My phone showed the same Gmail synching error after failing to install a new, relatively large application. Some applications worked, but others did not. The phone couldn't synch Gmail and also reported a stubborn and mysterious low memory warning that rebooting and clearing application caches multiple times didn't resolve.
I ultimately returned the phone to its normal state by uninstalling the most recent application from its listing in Settings -> Applications -> Manage Applications
. This uninstall likely removed extra files that were both taking up space and interfering with Gmail. (I assume this is just one problem a failed or crashed install can cause.)
Once the uninstall finished, my phone dropped its low memory warning and started synching properly again. I was then able to reinstall the uninstalled program successfully, without further memory or Gmail problems.