El problema puede ser que todavía estés usando la versión beta del MSN Messenger. Prueba descargándotelo de la web oficial:
http://messenger.msn.com/Download/
Hay unas FAQ's que trata los problemas de conexión:
http://messenger.latam.yupimsn.com/Help/#LQ9