Apparently due to a bug in some google+ version app Android had a problem syncing.
After the bug fixed and a reboot I kept having the same problem so here is how I fixed it on android 4.0:
-go to settings -> apps -> (sort all apps) gmail
-click on "clear data"
-insert the password
-wait for a sync
you are done