I was working on a server doing some cleanup of old applications when I was suddenly not able to uninstall or install applications anymore. I would get an error about the Windows Installer Service failing. I have a quick glance at the event logs and found this gem of an error:
Event Type: Warning
Event Source: MsiInstaller
Event ID: 1015
Description:
Failed to connect to server. Error: 0x8007041D
This error does not give a huge amount of details, but according to Microsoft it translates to “The system cannot find the path specified“. 

I tried several fixes including running the following commands. You must have the services console closed or it will not properly reset the service.
msiexec.exe /unreg
msiexec.exe /regserver

This did not correct the issue, I next found a direct uninstall command and executed it manually from the command line adding logging to the the command to see what the installer service was having an issue with.
c:\Windows\System32\msiexec.exe /i {ProductCode} /L*v c:\temp\msiexeclog.txt

This returned the following error code:
MSI (c) (44:98) [16:16:41:018]: MainEngineThread is returning 1601

I have now reached the point that it looks like reinstall of the Windows installer would be the fastest solution, to do this I first cleaned the old installer from the system using the following commands.
cd %windir%\system32
attrib -r -s -h dllcache
ren msi.dll msi.old
ren msiexec.exe msiexec.old
ren msihnd.dll msihnd.old

After restarting the system I downloaded and installed a new copy of the Windows Installer from Microsoft. After one more reboot I was able to continue application uninstalls on the server.