That happened to my wife's Droid too, she tried all the standard things like re-setting settings, re-booting, battery pull. Mine was working fine. Her's began working after a couple of hours.
If that doesn't work go into settings - apps - and select filter all under the menu softkey. Then on the 2 gmail apps click on them and clear the cache... this fixed mine
Make sure that all of your sent messages are already sent. My gmail did that once and there was a message that hadnt sent and caused gmail not to sync.
Yes, if there is an email stuck in your outbox it can cause this. Otherwise, clearing Gmail Storage data should clear it up. Under 2.01 some people were seeing this problem once in a while with certain wifi routers. Solution: don't use wifi. I thought it was fixed w/ 2.1 though.