Después de probar mil y una cosas, la solución era tan simple como:
Ir a:
C:\Documents and Settings[b]User[/b]\Contacts
Borrar la carpeta de la cuenta que daba problemas (en mi caso la mía, desde otros id sí que me dejaba conectarme).
Recordad que en algunos casos la carpeta está oculta.
Y ya está.
