Basically you have to add the msnnsgr.exe program in the firewall exceptions - (classic view) Control Panel > Windows Firewall.
If it's still not connecting, try the following found on Microsoft newsgroups.
I found the procedure below in another group, and it solved my problem with Vista and Live Messenger. Apparently Vista's "auto-tuning" networking feature doesn't play nice with some routers. Not sure if it is a bug in Vista, a bug in Messenger or a bug in the router firmware but anyway this looks like a possible workaround that might help other people who have the same problem. BTW I have a NetGear DG834
- Click start
- Type: cmd
- Right-click cmd.exe when it appears under Applications
- Click Run As Administrator
- Type the following:
netsh int tcp set global autotuninglevel=disabled
- Press enter
- Restart your computer
To check autotuning is disabled repeat the above but type:
netsh int tcp show global