Authenticator not working on new phone

Question

I just purchased a new Android phone and am trying to set up my Microsoft account on it. I was seemingly able to set up Authenticator via a QR code on my computer screen, but when I then try to sign in to Microsoft apps on my phone and click "send notification," I never receive the sign-in request on Authenticator. The issue isn't with notification settings on my phone; I try opening the Authenticator app and still see no sign-in requests. And I've now spent a few hours repeating this process again and again with no luck.

I chatted with a Microsoft tech support rep who thought the issue might be that I had Authenticator installed on my previous phone, which stopped responding to touch and which I did a factory reset on. Is there some way I can reset Authenticator for the new phone, assuming that's the problem?