I had just had a problem like you described with Google Authenticator, where I got a new phone and I couldn't turn on my old dead phone for its Google 2FA; I was totally locked out of the service until I found a way to briefly get the old phone to start.
Authy would have let me just use my new phone! Here's a trick for those still wanting to use Google Authenticator- when you sign up for a new account, save a screenshot of the QR code; that way I think you'll be able to recover on a different phone if you scan that (just remember to store the QR code safely!).
"store the QR code safely" being the key phrase here!
Good that you finally got into the old device, and not a bad idea if still using google to store the QR code offline!