I guess some screenshots should help there.
Step-by-step explaination (Close your messenger before):
1. Click Start.
Screenshot
2. Click Run
Screenshot again
3. Type: "C:\Documents and Settings\<TYPE_YOUR_USERNAME_HERE>\Local Settings\Application Data\Microsoft\Windows Live Contacts"
Screenshot
Don't forget to replace <TYPE_YOUR_USERNAME_HERE> by your computer username!!!
4. Delete all the files that you see in that folder.
Screenshot
And then you are done