I take it you have XP Home. Go into Add/Remove Programmes and select the option on the left which says windows components. Takes a few mo's to get into it and then scroll down the list and then uncheck Messenger.
Then restart machine in the program list from the start menu you will possibly still see the older icon, right click and delete this.
That should sort it. If you have been using both then you will also need to uninstall live messenger in add/remove programmes and reinstall this.