Looks like Google did a not so nice thing. The Google Authenticator app no longer will generate the codes for some items, including Google's own account. This happened after they offered to backup all items to their cloud in case you lose your phone; if you don't do that, their app will break itself like this.

Two-factor authentication is about 'one thing you know and one thing you have'. The first thing is your password, the second thing your phone. The generated codes on your phone prove that you have your phone. Backing up the app in your Google account renders the latter useless and puts you back at one-factor authentication.

Of course you can and maybe should backup the secrets stored in the app. But that must be on 'something you have' and not somebody's cloud.
#GoogleAuthenticator