Hi,
Unfortunately you're not the only one experiencing this problem. I posted some instructions
here you can try.
Could you do me a favour and sign in to a web messenger, like
http://ebuddy.com, and see if your contacts are still there?
If they are, then that means they haven't been deleted, just Windows Live Messenger can't view them for some reason.
Chris