Download the cleanup utility from microsof:
http://support.microsoft.com/kb/290301
Once it is installed launch it from the start menu. Look for any installations for Windows Live Messenger and click remove. Once this is done you should be able to reinstall Windows Live Messenger.