[Hawk]

what account are you configured through, and how are you setup? IMAP or POP or the pre-config in the iPhone?

I used to get the same message as well, usually if I was a little faster than the download- in otherwords, impatient.

I now have 2 IMAP accounts for Gmail setup, and one POP, and everything works fine, and I don't recall seeing that message since.

First recommendation: Do not use the preloaded configs on the iphone. Even Google recommends not using them.
Second. If you are using the POP configs, try using the IMAP instead. You will have all your folders, and your mail can be "synced" to the server, so if you access from your PC, it shows the same on your iPhone.