Désinstalle Windows Live Messenger, et télécharge le package directement des serveurs de Microsoft, ça assurera que le package est bien valide. Puis réinstalle-le.
http://download.microsoft.com/download/8/1/0/810b7b24-256c-4db1-8dcf-d342db3b6717/FR-FR/Install_Messenger.exe