The Windows Installer Service needs to be running in order to uninstall in Safe Mode. This solution will start the service.
Windows 8 users: Press the Windows key + Q to open an app search and type cmd into the Search field. Right-click the cmd application when it appears in results and select Run as administrator from the context menu.
REG ADD "HKLM\SYSTEM\CurrentControlSet\Control\SafeBoot\Network\MSIServer" /VE /T REG_SZ /F /D "Service"
net start msiserver