Mira por si acaso en tu guenta de gmail si los tienes guardados
Yo cuando me robaron el movil recupere asi los contactos todos
Entras en gmail y pinchas en la flechita que te aparece al lado de Gmail (arriba a la izquierda) y en el desplegable en contactos
PD te lo digo por si acaso pero depende de si a la hora de guardarlos le diste a guardar numero en tu cuenta de gmail
Edito: Tiene que ser desde el ordenador, perdona