try running Zap Messenger* to completely remove Messenger then reinstall it as the problem could lie in a registry entry or something, it doesn't hurt to try
incidently, did you patch your MSN at all?
*
http://messengergeek.spaces.live.com/blog/cns!E37...entry?sa=444854878