first of all it sometimes it says this because mirosoft are updating and what not but if it fails to work for a whole day or more then it wouldnt be that.
As chap said above check that your firewall isnt blocking it and make sure msn messenger is in the "allowed list".
Msn is known frequently to do this.. it took my friend two weeks to actually talk to someone from msn... somehow the password changed... but yea the sign in at this time thing is what happened to me and still does to this day.. so they closed my account for no reason...