First, there are actually multiple ways how 2FA might work, the maybe simplest way is to receive a SMS with an access code form your service during each of your logins. While this is a bit less secure because it could be intercepted, this way you should not be required to update your 2FA settings if you switch your phone while keeping your SIM.
Another way how 2FA could work is by installing a token generator on your phone, an app from your service provider. For instance an Time-based One-Time Password generator. The point here is that your phone can generate a token at anytime even without network access.
Since such a generator works the same on all phones and is a deterministic algorithm, some code or key on your phone is required to verify it was indeed generate on your phone. If the app would use some thing like your calling number everyone knowing it, might generate a valid code for your account. Also serial numbers of your SIM or hardware have similar flaws. So a better way is to have a random key only available on your specific phone and in some sort at your service (for verification). Btw this usually makes not only losing your phone an issue but also deleting just your generator app.
However, such a key means that changing your phone necessarily means that you would have a different installation of that app on your new phone with a new key (or non). And for security reason, your old key shouldn't be available to any syncing service, so there rather should be no mean to copy it over.
Reason why the recovering of your account is that complicated, is that it is by definition a way to by-pass the 2FA. That means if there were an easy way for your to recover it, there is also an easy way for the bad guys to get access to your account while you are using 2FA. By entirely denying this (like Github), it guarantees for your that once you enabled 2FA there is hardly a way for others to by-pass it.