Just another thing I've noticed when I had this problem. I tried all of the tricks mentioned above, clearing data/stores in gmail and gmail storage. Worked for a couple of minutes, then no sync again. Also wiped and tried that, no help long term, just a short while. So, I did some looking around on the net and noticed that at times, this can happen to contacts and the calendar as well if something somewhere gets corrupted.
So, I went into my gmail via desktop browser and seriously cleaned up my inbox. I had a bunch of emails that I was able to either delete or sort/archive. Once I did that, everything started running smoothly and syncing properly again. I'm betting that I had an email that was somehow stalling the whole sync process.