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.
So I logged out my YouTube, then log back in with my new password.
My problem solved.
However this still doesn't solve the security issue brought up by many here.