In that case some anti-adware program probably damaged the sponsor uninstaller, but uninstalling Live Messenger is not required.
Do this:
- Disable all anti-adware / anti-virus software and any other program that might be interfering with the sponsor.
-
Download Messenger Plus! and install it with the sponsor enabled (just install it again over your current installation, this will fix the damaged file)
- Now got to Add and Remove Programs in Control Panel and try again.
See
How to uninstall ad-ware/sponsor for more info.
/ 
