ZapMessenger is only of any use if a full uninstall doesn't actually happen. Using it to remove messenger is the incorrect way and may cause more problems than it solves.
Remove WLM the correct way (Add/Remove Programs) and then make sure there are no remnants left of it in the Program Files folder (Program Files\Windows Live\Messenger) and that it is not in the registry still (HKCU\Software\Microsoft\Windows Live Messenger)
If, when you re-install, it does not work still, it is not an error with the installation. In this case it would be wise to send feedback to Microsoft about the error using
this link, as otherwise they will be unaware of any such problems and will be unable to help in the future.
/ 
