You've not stated which firewall you're using so it's impossible to provide exact instructions. Basically, you need to go into the firewalls settings and examine the log which lists blocked software. When you see the reference to Windows Live Messenger, you should follow the procedure for changing the status of the program, so that it can access the internet. This will vary with different firewalls but try right-clicking on the the reference to WLM and looking for an option to 'enable access'.
Chris