I had two gmail accounts synced. I deleted one by accident, and when I tried to re-add my gmail account under gmail or settings (under accounts and sync) it would hang and give me the same error message as you. It wouldn't connect to Google even though my connection was fine. I did some research, and apparently it's not an uncommon problem. The workaround that exits is to register your Google account through your YouTube app, after which your gmail for that account will be synced now. Try it, it worked for me.

Sent from my GT-I9000M using XDA App