1. Boot into Safe Mode.
2. Create the following registry key (it won't exist by default, so create this new key):
HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\SafeBoot\Minimal\msiserver
(If you also want it available in Safe Mode w/ Networking, add the "msiserver" key under the HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\SafeBoot\Network\ key found here as well)
3. Edit the "(Default)" value in the new "msiserver" registry key, and enter "Service" in the "Value Data" box. Click OK, and close the registry editor.
4. Reboot back into Safe Mode, and the Windows Installer service should now run and allow you to add or remove programs in Safe Mode.
If you STILL can't boot after uninstalling your product at this point, _THEN_ you might want to consider a repair install or a rebuild.
There is also a small (free) utility called SafeMSI that will start the installer service in safemode. I've been using it for a while and it's quite handy.