Fíjate si los contactos creados con el teléfono están guardados como "contactos Google", no como "Teléfono" o "SIM" o de otras cuentas que puedas tener. Lo digo porque si no son contactos de google, pues luego no se sincronizan...
Parece una tontería pero conozco gente que le ha pasado, porque estas cosas no las explica nadie... Y con las prisas para introducir un contacto, pues uno no se fija.
Si no fuese eso, pues no sé qué puede ser... Quizás comprobar que no sea que tengas dos cuentas de gmail y los contactos, o algunos, estén en la otra cuenta.