A firewall can block incoming as well as outgoing packets.
As for aMSN, I never used it. So I can't help.
But have you checked the web site and the documents, maybe it is a problem with the software.
Or it could be that the MSN network is blocking you for some reason...
Also, do you have the most recent version ?