If you use google apps for business and your services were part of the big migration fiasco then you might have found yourself in the same situation I was in.
After changing my google account password I somehow had a google apps account with my new password, and an old personal account with the same username, but old password.
If you can log into gmail using your old password, but are then prompted to rename your personal account or migrate services then this has probably happened to you.
I'd already migrated stuff previously, but I hadn't renamed my old account. I thought it would have died by now.
I logged into my old account using current user name and old password. When prompted to rename my old account I did so. The next time my phone tried to log in the username old password combo was no longer hooked up to an old account and it asked me to enter a new password.