Okay, I think I may have figured this out. Try it, see if it helps.
I've been having this same issue for about 2 weeks now. I didn't think much of it at first, until I tried going to the Play Store and found myself unable to get in because of it. That was annoying.
Today I went and checked my sign-in status for Chrome, and found that it was also messed up. The program told me I needed to create an application-specific password in order to make it work.
I've seen this recently, and shrugged it off at first. I have enough issues keeping track of the passwords I already generate.
Well, this one forced the issue on me, so I went
here, clicked on the Authorizing applications and sites page link in Step 1, and logged into Google like I normally did. It gave me a password, which I entered into the Chrome sign-in where it asked for it.
And voila! Chrome was re-synced and working like a charm!
Now, it mentions that this is also for use with some smartphone apps, including Gmail on your phone (and, presumably, others). So, I generated another one, tried to open up the Play Store, and entered the newly generated password where it asked me for one.
It worked!
I'm guessing therefore that the app-specific passwords are what you need to use some apps on your Android phones. If I'd known this 2 weeks ago, I would have saved myself a lot of frustration. Give it a try, and I hope it helps. Hopefully this issue will be put to rest.
Best of luck.