To solve the problem, you need to log into the account using another method other than the authenticator (password or Windows Hello (biometric), or text/email a code, etc.), then delete the authenticator option titled 'Send sign-in notification' from the list of verification methods in the account security section.
Once you've removed the old, invalid authenticator selection from your account the problem goes away, because it's no longer there to be used and you can set up the new phone's authenticator.
The reason it happens is simple, you got a new phone and didn't take the time to find out first how to properly switch from one phone to another or couldn't because you lost the old phone.
For one, thank you for accusing everyone with this problem of not taking the time to figure out how to do this correctly. I mean, it's not like anyone's phone ever breaks or anything, right? For two, what are you supposed to do if you cannot use the number currently attached to your Microsoft account? Not everyone has control over these things, and you being accusatory and posting answers that only work in certain situations is not very helpful.
Sorry, I know I'm being standoffish, but I've been trying to solve this problem for a while and you simply assuming that everyone who is having this problem is just lazy, when in reality I cannot afford a nice phone and my cheap one broke, is quite frustrating to me.
Estella Helton,
I long ago learned that being 'nice', saying I'm sorry and other platitudes do nothing to teach the basic truth that people need to take responsibility for their own mistakes, which is why my often relatively abrupt and stern methods.
However, if you read carefully, the final portion of my text you included above ends simply as; "or you couldn't because you lost the old phone.", which inherently gives you the out that, of course, you can't possibly do this correctly if the phone is lost, stolen or unrepairable.
Unfortunately, Microsoft is so prone to the same useless platitudes and friendly methods, that they didn't simply block you from using your account long ago until you provided at least 3 ways to authenticate other than the authenticator, so it's unlikely you'll ever end up in the situation you and many others have by not maintaining multiple working ways of regaining access when real life creates such obvious situations as lost or damaged phones.
Since I'm a past computing and security professional, the fact these sorts of account lockouts could occur was obvious to me, so I long ago added not only the default phone number and email options, but also others on top of the authenticator which as you've learned can disappear with the phone itself. That includes the optional Recovery Code and alternate email address, for which I use my Gmail account that also supports the smartphone itself.
The question for you at the moment is whether you had enabled 2-Step verification in your Microsoft account, because that means you'll need to have 2 methods of verification available to recover your account, while if you'd only used the authenticator app without enabling 2-Step, you'll only need a single method and can also try using the account recovery form and self-help information regarding that found in the following document.
Note the following at the start of that page, since it may work without needing to use the form.
Tip: This information assumes you've already tried our Sign-in Helper tool. If you haven't, try the tool first.
Help with the Microsoft account recovery form - Microsoft Support
Please read the 'More tips' section below the 'Account recovery form' button on that page before starting with the form, since that tells you how to increase your chances of success.
If you're having trouble using the form, create a new, separate thread in these same forums for help, no one else in this huge thread wants to continue to follow this conversation and other people who are better at using the form than me can aid you with it.
Good luck,
Rob