I had this same problem and it drove me nuts until I went to the Windows support page and it said the problem could be as simple as the date and time stamp on your computer being wrong. SO I checked and sure enough the date on my computer was a month ahead. After I set it back VOILAAA like magic I could sign into Windows live Messenger!!! Here is the link for anyone who wants to try it, it worked for me!!!
