Well whadayaknow, i was trying to help Annuix (who i added to my WLM list when i left SP3 forums) with the very same problem last night (told him to try several things, don't know if it worked yet as i had to get some sleep)
What you could try is delete the contact caches/folders (the ones that correspond with your passport) of WLM 8.1:
%userprofile%\contacts
%userprofile%\Local Settings\Application Data\Microsoft\Windows Live Contacts
(start > run..type folders in as i put them above and hit enter to go there directly)
If these haven't been deleted when you uninstalled WLM 8.1 (note these are hidden folder so make sure you turn on "show hidden files/folders"). Then try to sign in again (will take a bit longer as it has to get your contactlist from the server).
If that doesn't work you can try the most drastic approach: a fresh install!
See
Completely remove (MSN/Windows Live) Messenger
Good Luck! Post back wether or not it helped and wich method did.
/ 
