Mi teléfono mostró el mismo error de sincronización de Gmail después de no poder instalar una nueva aplicación relativamente grande. Algunas aplicaciones funcionaban, pero otras no. El teléfono no podía sincronizar Gmail y también informaba de una obstinada y misteriosa advertencia de poca memoria que no se resolvía reiniciando y borrando las cachés de las aplicaciones varias veces.
Al final devolví el teléfono a su estado normal desinstalando la aplicación más reciente de su listado en Settings -> Applications -> Manage Applications
. Esta desinstalación probablemente eliminó archivos adicionales que estaban ocupando espacio e interfiriendo con Gmail. (Supongo que éste es sólo uno de los problemas que puede causar una instalación fallida o accidentada).
Una vez terminada la desinstalación, mi teléfono dejó de emitir el aviso de poca memoria y empezó a sincronizar correctamente de nuevo. Entonces pude volver a instalar el programa desinstalado con éxito, sin más problemas de memoria ni de Gmail.