Try uninstalling Windows Live Messenger and Messenger Plus! Live from Control Panel > Add Remove Programs. Then delete folders 'MSN Messenger' and 'Messenger Plus! Live' in \Program Files\. Reboot your computer. Then download
Windows Live Messenger and
Messenger Plus! Live. Install Messenger, see if it works, then install Plus! Live and see if you have the same problem.