You're saying with msn messenger 2009....
Is there a reason you can't run the current version of msn messenger/windows live?
I'm using Avast love it and I have windows live/messenger installed, actually just put on the newest version last night. I'm using Win 7 64 bit. I'll admit I did have issues with one of the older versions of msn though so perhaps an update of that will resolve.
Just my $0.02 though.
It may have been also that you had the firewall in Avast set to block the port msn was trying to use to connect.