Hey man, I got the same problem:
Can't log in to my account on MY pc,
Can login to other accounts on MY pc,
Can login on my account on OTHER pc's,
i just read that other ppl have this too with windows live messenger, and the solution is indeed to uninstall, and remove the Contacts list
(its mostly common that this list is in: C:/Documents and Settings/[your username]/Contacts/[your emailadress of windows live messenger] I deleted my own hotmail contacts list, and it worked great!
(ps, make a backup of your contact list or maybe you will suffer side effects such as account block or somehting)
well, good luck =D