Pues igual tu problema está en la sincronización con Gmail. A mí no me funciona como debe o como yo esperaba.
Una vez bajados los contactos de Gmail al teléfono, si borro o edito los contactos en el teléfono, a veces sincroniza todo hacia Gmail, pero casi siempre lo que me pasa es que se vuelve a descargar todo tal como estaba en Gmail, con lo que pierdo todos los cambios hechos en el Galaxy.
Así que ahora solo pongo 'orden' en la agenda de Gmail, y luego sincronizo.
Sent from my GT-I9000 using Tapatalk