Typically you will get a no internet connection error if you are not on Wi-Fi or data. I can pretty much guess that is not the case because I have gotten those errors myself while I looked at the phone in dismay. The same with the invalid credentials error and wrong password error, etc. (Hello, I think I know my password... very frustrating).
I am assuming you are using the stock email app that came with the phone. If so, go into that app in settings, uninstall updates. Go back to your email app to see if it is working. If not,
-remove your gmail account. May be in email settings under Gmail sync, change sync settings or remove account. Click on your gmail, go to menu, remove account.
-Go to play store. You will have to sign in using your gmail (existing account), check your drop down notification for "permission requested" orange triangle alert. Tap on that to allow access. Go back to play sure and Install the email updates.
-Go to accounts and sync in settings. Tap on your gmail to set up your sync.
-Go back to your gmail to see how it works.
If this isn't successful then you may have to do a factory data reset. But don't do that until you make sure you have everything backed up that you want to save. As a guide for ideas on backing up and restoring before doing an fdr see:
http://www.droidforums.net/forum/rescue-squad-help/219101-getting-most-success-upgrading-ics-gb.html
Sent from my DROID RAZR Maxx using Droid Forums