I know this is an old thread, but since this has happened to me twice now and this was one of the first hits I got on a Google search for the problem, I felt I should post the solution that worked for me in case anyone else runs into the same issue.
Everything was set correctly for me: sync settings, account info, etc. A manual refresh had no effect. Mail would come in normally on my phone, but when I deleted it from the phone it wouldn't sync the deletion with my Gmail inbox on the website. In both cases, it worked properly for a while before the sync failures began.
The solution I ultimately discovered was to go into the Market app, search for Gmail (it did not show up in the "My apps" list), and open the link for the official Gmail app. It showed that there was an update available, so I downloaded and installed it. After that, sync works perfectly. Either there was a bug that got corrected in the update, or something got borked on my system and was reset when the update got installed.
Both times this issue happened, it was after I restored a Nandroid backup of the stock configuration on my Droid X. No idea why it would cause that behavior to occur, but since flashing other ROMs hasn't created the issue it seems worth mentioning.