Windows installer problems

Whenever I try to download a program I get a window that opens and says:

The Windows Installer Service could not be accessed.
This can occur if you are running Windows in safe mode(I am not),
or if the Windows Installer is not correctly installed(probably the case).
Contact your support personnel for assistance(I did and they said that I needed to do a complete system wipe and reinstall Windows XP with my recovery disks - which I have, but the least I can get this done for is $99 - which I do not have - from HP.).