I have spent ages yesterday and today having the SAME problem as described here. Such a stupid system when you can't just upgrade your phone without hours of drama trying to use your auth app on your new phone. Why does it not just transfer to your new phone like other apps? Is it 2010 and nobody told me?
After wasting so much time I now have to get my administrator (who is in a different country) to try the option mentioned and try again tomorrow.
Really unhappy with Google atm.
No mention until one of the answers above that you need to be an administrator of the account or have the account set up so that 2SA is an OPTION. And no indication on any google search as to how to get back up codes, or QR codes. There needs to be a change in approach to how this app transfers from one phone to the next. Google should be making this easy for dumb users like me.