Office365ログイン時にAuthenticatorでサインインできない

PCからOffice365で管理画面にサインインしようとする際、コードの入力を求められ「モバイル デバイスの Microsoft Authenticator アプリに表示されているコードを入力してください」​となり、スマホのAuthneticatorアプリを起動しました。

一月前にandroidのスマホを機種変更していました。Authenticatorアプリを入れなおしましたがバックアップからの復元ができないため、PCで開いているアカウント名を改めて入れてAuthneticatorにログインしようとすると、「Microsoftアカウントが存在しません。別のアカウントを入力するか、新しいアカウントを作成してください。」と表示されてしまい、ログインできません。

別のスレッドで、長期間利用していないアカウントがそのようになるような説明がありましたが、定期的に開いていたので該当しないと思います。

PCでログイン時「ID を確認する」から「別の方法を試す」を選択し「確認コードを使用する」にしても、結局「モバイル デバイスの Microsoft Authenticator アプリに表示されているコードを入力してください​」となってしまい、Authneticator上で確認できません。

そこから先に全く進めず、困っています。

Authneticatorアプリは最新です。

何卒御教授よろしくお願いいたします。