Miałem tak samo. A dokładnie kontakty były w telefonie, ale nie synchronizowały się do gmaila.
Zrobiłem zapis/eksport kontaktów na kartę SD, potem wykasowałem wszystkie z kontaktów. A potem ponownie zrobiłem import, ale zaznaczyłem, że import do konta gmail, a nie do kontaktów.
Zaimportowało i kontakty wylądowały po synchronizacji także na serwerze gmail.