when you uninstalled Messenger did you by any chance go to C:/Program Files/MSN Messenger <-- an delete that folder also? if not try deleteing that after u uninstall the messenger from Add/Remove, but honestly, i think its a MSN Messenger server problem cause i have had problems with it loging me in very slowly, but that p[roblem has now gone away , but trry
http://webmessenger.msn.com/ an check there that you can login through that,
