Turn off the firewall completely, so it allows everything, then connect with your MSN client..
now open a console and type "netstat -p"
have a look for an entry like so...
tcp 0 0 192.168.1.2:32773 baym-cs385.msgr.ho:1863 ESTABLISHED 3922/kopete
tcp 0 0 192.168.1.2:32774 baym-cs94.msgr.hot:1863 ESTABLISHED 3922/kopete
i use kopete.. but you should see somthing like aMSN where mine says Kopete.
look at the number after the ":" on remote address. make sure that your firewall is set to allow outgoing TCP connections to that port (in my case 1863) i think your port will be the same, but it may not.
now sign out of aMSN, turn the firewall back on, and try to re-connect. does this work ?