First of all, check that the time of your computer and date is correct. Sometimes MSN Messenger will prevent you logging in if there is a large discrepancy.
Failing that, try going to Start > Run and typing:
regsvr32 softpub.dll
If that fails, get TaskManager open (start > run > taskmgr ). Sign in to MSN Messenger, and as soon as you start the sign-in process, kill msnmsgr.exe (end process). For some reason, I've found this to work when I have those kinds of useless error messages.
If that still doesn't work... let us know!