First off, do a Windows Update.
The 3.1 you are on about is the Windows Installer, you can
download Windows Installer 3.1 here.
Supported Operating Systems: Windows 2000 Service Pack 3; Windows 2000 Service Pack 4; Windows Server 2003; Windows XP; Windows XP Service Pack 1; Windows XP Service Pack 2
After you installed that (make sure you install on an account with admin priviledges), reboot and install Windows Live Messenger again from
http://get.live.com/messenger/
Should you have Windows XP Service Pack 2, Windows XP Service Pack 3, Windows Server 2003 Service Pack 1, Windows Server 2003 Service Pack 2, Windows Vista, Windows Vista Service Pack 1, or Windows Server 2008 you can install
Windows Installer 4.5 Redistributable.
Make sure you download (and install) the correct version: OS, language and bits!
Also note that Windows Live Messenger will not run (is not ment to run) on anything below Windows XP SP2.
/ 
