Los contactos los guardas todos en la cuenta de Google? Si fuera así por mucho que cambiaras de rom o hicieras restablecimiento de fábrica, seguro no deberias perderlos..
El Whatsapp los coge de la agenda, así que si los pierdes de la agenda, normal que pasen esas cosas en el whatsapp