My guess is you needed to remove the sandboxed uninstaller from the sandbox so it could do what it needed to do. Comodo Programs Manager has a Forced Uninstall option, though. It's in the settings.
The programme in question is Speedbit's Video Downloader.
The item is only sandboxed if the Web is not available. I am not sure I _know_ remove something from the sandbox.
I tried it with Forced Uninstall selected. Again this was with the web off in CIS. I had the same message about needing to reboot. Then I waited and up popped a message saying that the uninstall had been successful. However then the programme tried to open Internet Explorer. That failed, with IE "not responding". When I went back to CPM, there was an error message (no ID on what programme had it) Runtime error 217 at 04F7378B.
Again CPM had frozen and had to be restarted to work.
However this time, the programme HAD been deleted. So workable but messy. The problem seems to me to be that CPM still allows the uninstaller of the programme to try to do the job. The other uninstaller I use will simply jump straight to removing all files and registry references, if in forced removal mode. Hence less control by the uninstalled programme and less mess.