Contactos desaparecidos de skype tras formatear un pc

Buenas tardes, a ver si soy capaz de explicarlo
Hace unos días tenia el ordenador un poco podrido, necesitaba ser formateado... Después de lo cual, volví a instalar el mismo sistema operativo y los mismos programas, pero tras instalar skype pude ver que todos los contactos que tenia habían desaparecido.
Es bastante raro, pues no se guardan en el disco duro, sino en servidores como me explico el servicio de skype, ellos dicen que restauraron mi cuenta, y me consta que no se borro, pues mis antiguos contactos me ven conectado, aunque yo no les tengo aparentemente ni siquiera agregados...
Pues eso, agradecería cualquier idea o similar...