Buenas,
Me pasa lo mismo y voy a probar lo mismo y os cuento.
Shilox, los contactos se guardan en tu cuenta de Gmail por lo que en cuanto vuelvas a meterla los volverás a tener ahí.
EDITO: Todo perfecto después de quitar y poner la cuenta de Google. Gracias!