El problema es que tus contactos están guardados en el teléfono, no en tu cuenta de Google.
Yo creo recordar, creo que lo que hice fue, desde la app de contactos exportarlos y luego importarlos eligiendo mi cuenta de Google. Una vez que hayas eso puedes ir a cuentas y sincronización y hacer la sincronización de contactos, pero como veo que la tienes automática supongo que la hará solo.
Lo que sí te recomiendo es lo siguiente, una vez que hagas ésto ve a la app de contactos, oprime Menú y elige "Opciones de visualización", allí activas que se visualicen solo tus contactos de Google y si quieres algún grupo en específico. Luego ahí mismo elige "Mostrar solo contactos con números telefónicos" porque sino te aparecerán tus contactos regulares incluidos del teléfono y las cuentas de e-mail de tu cuenta y puede resultar molesto.
Cuando agregues contactos verifica que sale que irán a tu cuenta de Gmail y no a los contactos del teléfono sino pasará lo mismo que te ocurre ahora.
Espero que te sea de ayuda.