Se vai nell'applicazione telefono, riesci a vedere la rubrica con i contatti?
Hai cercato in Impostazioni > Applicazioni che la app ci sia e non risulti per es. disattivata?
Non dici che versione di Android hai, comunque fino alla 4.4.4 l'applicazione "Contatti" si chiama "Persone".