This happened to me when i moved from one phone to other. on investigation i understood that google only allows one authentication device. as on the old phone this setup was already done, The only easy option is to move the authentication to a different phone.
Following is the few step process that worked for me.
- Open Authenticator but do NOT press the “Begin setup” button.
- Instead, select “setup account” from the option menu.
- Then from another device/computer, go to https://accounts.google.com/b/0/SmsAuthSettings, select “Move to a different phone” and scan the QR code.