Microsoft Authenticator requires a code when I register a new account

Question

I have recently changed mobile phones, and did not activate MS Authenticator on new phone before deleting from old phone (and don't have access to old phone anymore). Now I want to add an account to MS Authenticator on new phone, but it continually asks for a code from the Authenticator, and alternative methods give the following error: "Sorry, we're having trouble verifying your account. Please try again."