Uninstalling it may not work. If you check your Application Event Log, it will likely see Event ID 447 (Database corruption), referencing <your profile path>\Local Settings\Application Data\Microsoft\Windows Live Contacts\{xxxxx}.
Take note of the path. Exit Messenger. Then in Windows Eplorer, delete the indicated folder {xxxxx}. Start Messenger, it should re-build your contact db.
