To resolve the situation:

Turn off any spyware detection programs.
If you have the Microsoft® Windows® AntiSpyware (Beta) installed, right-click the Windows AntiSpyware icon in the taskbar notification area and click 'Shutdown Microsoft AntiSpyware'.

To turn off non-Microsoft anti-spyware programs, refer to instructions provided by the manufacturer.

Run MSN Messenger Setup again.

Not a very user-friendly error message if you ask me, but then does such thing exist? Anyway, I haven't verified the suggested solution, but here it goes:

1) Click Start > Run
2) Type msiexec /unreg and press enter and wait until it appears to have finished.
3) Go back to Start > Run
4) Type msiexec /regserver and press enter.
5) Try to install MSN Messenger 6 again. Good luck!