The internal firewall of your router is causing this by blocking the ports that IM uses.
You should open up these ports in the firewall configuration model of the router. To know which ports you need to open, check this list.


I used to use MSN and found out that it practically required me to open all my ports if I wanted it to work right. (especially if I wanted to use video conferencing).

In the end I just ended up putting one of my PC's in the DMZ and putting Zonealarm on it to still give it some form of protection.