Sounds to me like your Authenticator app link was broken. Had that happen to me when I did an upgrade of my phone. The phone name stayed the same and the app was restored but the underlying link was broken. Had to completely remove it from the MS security portal and readd it.