I have just been working with this exact issue. Whenever I tried to register a Global Admin account (Unlicensed just used for Admin) with Microsoft Authenticator I would get this error.
Also if I tried to use SMS for MFA it would fail with a generic error message.
I then happened to be in Entra and looking at the accounts Contact info (Luckily we made another Global Admin account that works) I noticed the email address for alternate address was out of date. When I tried to edit that and save it I got a more useful error:
Failed to update user
Update would cause the user to have a proxy address already present on user "John Smith". Click on the notification to see the conflicting user.
So it turned out that the Global Admin's login account was ******@tenantdomain.co.nz where there was a user with the same as an Email alias. As soon as I deleted that email alias everything started working with the main admin account.
Obviously in the past 365 allowed you to have a non-licensed user with a username that was the same as an email alias assigned to a mailbox but not that breaks things with AzureAD/Entra and MFA etc.
I've changed the Global Admin's login name back to the onmicrosoft.com FQDN so hopefully I'll be able to put the users email alias back at some point.
I spend a bit of time bouncing errors back to a 365 support person and was just at the point of it being escalated to someone from the MFA team when I got that more useful error when attempting to give her more info.