I had this problem too and after spending hours searching the internet and not finding anything that helped me, I think I finally stumbled onto my fix.
I use Firefox as my browser. With Messenger being a Microsoft program, I started to wonder if the two were incompatible. So I closed my Firefox browser, opened the Internet Explorer browser and then tried to log onto Messenger again and it went through with no problems whatsoever. (Then I closed IE and reopened Firefox and Messenger is still operating).
I don't know if it will help you but I thought I'd pass along my experience. Good luck!