Antes de nada ¿te conectas directamente a internet o usas un proxy? si usas un proxy tienes que indicarle al messenger su direccion y el puerto a utilizar y el se encargara de pasar a traves del proxy.
De no ser el proxy no se me ocurre que puede ser, es verdad que existen directivas pensadas para impedir la instalacion o ejecucion del messenger, pero si puedes instalarlo y ejecutarlo, y solo te da error al intentar iniciar la sesion parece que el problema es de comunicacion. Asi que revisa que no tengas instalado algun firewall, antivirus, etc... que este bloqueando la conexion.
Y si todo falla prueba con otro programa diferente, por ejemplo este
http://amsn.sourceforge.net/, que es de codigo abierto y es un clon del messenger.