possibly your firewall is blocking the port MSN runs over (1863)
just a guess, though.

have you recently changed anything, security wise?

*edit*
oops,
just seen your edit