I had something similar to me happen and I was able to resolve it by myself.
I had Google Authenticate on my iPhone, it broke and so I bought a new phone. I switched over/kept my old phone number.
This still wouldn't let me login but when you try and login, you should be given "alternative" options to choose. I think I was able to opt for an SMS message, it sent it to that number on file, but if you only reset your credentials, your number is presumably the same? So selecting this SMS or Call option will work fine, and then once in, go to settings and edit the Authenticate, adding your new one and make it primary, then delete the old one.
Sorry I can't remember exact step by step and this is as close I can. Hope it can help - it was frustrating, so I know the annoyance and pain of it.