I had this problem 1 hour ago... but I discovered a way to go around it.

I changed my google a/c password from desktop, after that I have problems with all the google apps on my Galaxy Note, i.e. syncing, check my gmail, can't log in to google+, etc... However, I have no problem with my iPhone.

I was googling & come across this thread, seems no solution here either.

Tried to remove a/c but can't, except restore to factory settings (which like what EvaKe mentioned - incredibly inconvenient).

I was thinking if I only can just log out from one of the google app, then I should be able to log back in with my new password.

I was playing with all the google apps, which most of them don't have a log out function, except YouTube.