I've tried restarting, unchecking gmail sync, refreshing, syncing manually, etc..
It all started when I tried to send a large file using AndroZip via Gmail. It was stuck on sending so I deleted it. Since, then I double checked that it is out of my outbox and drafts.
I try sending a test message and it stays on "sending".
If I go to Gmail, I can see that I have new mail that's not being pushed to the phone.
Any help on this is appreciated.