Heyy reisan,
What did it for me was deleting the Messenger Contacts Cache folder.
http://messenger-support.spaces.live.com/default....d2009&sa=995514156
Click on this link, and there's a step by step guide to help fix the problem.
Hope this helps!
Msg back if there are and other problems.