I had the same issue. I forgot that I had Google two factor authentication and I had a different p/w for my phone. So log into your google account from a pc and get them to issue a new p/w for your phone by revoking the old one and getting a new one, type it in when prompted again on the phone and you're good to go.
You can start here:
https://accounts.google.com/b/0/SmsAuthSettings click on "turn off 2-step verification?"
You'll get this:
Turn off 2-step verification
You will no longer be asked for verification codes when you sign in to your
@gmail.com account. Are you turning off 2-step verification because of trouble signing into your account on your phone, or accessing your account on other apps? You may need to use an <<application-specific password>> with devices and applications that don't know how to accept verification codes.
<<application-specific password >> will have a hyper-link, click on that and that will get you to the right place to revoke the old p/w and get a new one.