Ok, go to Add/Remove Programs.
Remove Windows Live Messenger and Messenger Plus! Live
Restart your computer.
Download Windows Live Messenger 8.5 from
here and Messenger Plus! Live from
here.
Note: It's important to download from them exact locations.
Install both of them.
If that's no good, try using
CCleaner to delete cache and fix registry keys.