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