Su android spesso basta cambiare la visualizzazione dei contatti.
Dalla rubrica tocca il tasto funzione fino ad vedere la voce CONTATTI DA VISUALIZZARE.... controlla bene cosa ha impostato perchè magari ce li ha sul telefono e vengono mostrati solo quelli della SIM o viceversa.... in caso di dubbio basta impostare su TUTTI.