Reinicia el router. A mi me pasa y asi se arregla. Y mira que la fecha del pc este bien.
No, el msn suele ser muy complejo sobretodo este a mi me ha pasado algo parecido incluso situaciones donde se me conectaba todos mis contactos estaban como desconectados cuando estaban online.
Esto no se si te funcionara pero te valdria la pena probarlo a mi me funcionaron.
1. - Dale a Solucionar Problemas y mira a ver que problemas tiene, Si es algo del DNS te podria ayudar.
2. - Ves a esta ruta "C:\Users\[Tunombre de usuario"\AppData\Local\Microsoft\Windows Live\Contacts" y borra las carpetas que encuentres dentro. .
Repito dentro de "Contacts" puedes borrar todo.
3.- Usa el programa "Your Uninstaller" para borrarlo completamente incluido las claves de registro del msn y vuelve a instarlarlo bajandote el oficial de la pagina de msn.com