Last time this happened to me all I had to do was clear data/cache for the gmail app, uninstall it. Reboot. Reinstall gmail, then go to the account settings and turn off then on the mail sync. That's all it took for me.
I tried this, and it seems, at first glance, to have worked. I'm going to send a bunch of test emails over the course of today... will report back.
