Make sure the service itself is correctly started (It's called Windows Installer under services).
Then, what can be tried 1st is to re-register it:
Click Start, Run and type MSIEXEC /UNREGISTER, and then click OK. Even if you
do this correctly, it may look like nothing occurs. Then Click Start, Run and type MSIEXEC /REGSERVER, and then click OK. Even if you do this correctly, it may look like nothing occurs. Not a problem; try your Windows installer-based program again.
If that does not fix it, run a sfc /scannow for integrity check.
If that didn't work, some related reg fixes can be found here