When uninstalling and rebooting, did you also delete the MSN Messenger folder from C:\Program Files\?. If not, then uninstall both Messenger Plus! Live and Windows Live Messenger again. Delete both of their folders from C:\Program Files\ and then reboot. Then re-download them both and reinstall them fresh.
