Едва ли проблема е в телефона.
Провери:
1. Имаш ли Google Play на телефона при приложенията. Ако не - тогава няма да можеш да синхрозинизираш.
2. След като въведеш успешно пощата и паролата в акаунтите, отиди при акаунтите и натисни върху този с гугълската поща, след което ще ти се появи списък с нещата които синхронизира телефона. Там трябва да има и отметка за контактите.
3. Ако и това не помогне, вече бих си помислил че има проблем с телефона или със самите Google Apps, които са инсталирани на телефона.