This happened to me also.  I was using Google Authenticator with an exchange.  I upgraded to a new phone knowing that it would reinstall and import the setup for the keygen for the exchange.  I wiped my old phone and sent it off for recycling.  New phone came, set it up, and Google Authenticator did not reinstall.  When I reinstalled it, it did not transfer the config for the exchange.  So I tried a manual sync with my Google account.  No luck, gone forever.  Took me 2 weeks to get back into that exchange.  Fuck you Google Authenticator.