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.