Wraith_3: Any idea how to fix this?
Unlike others suggested, I wouldn't try to remove the game files manually or with 3rd party utilities like CCCleaner, at least not as the first thing. Instead, I'd first try to reinstall the game on top of the old installation (to the same folder), and then uninstall it.
This has worked for me in the few cases I've hit a similar problem as you. One such case was with e.g. KKND2 (GOG version), but I remembered the reason for uninstallation failing was because I had originally played it on another PC on the D: drive, and later I had installed the game on another PC (to C:) and copied the whole game folder from the first PC to that, in order to continue the game there. Apparently that also copies some config files suggesting the uninstall script that it is installed on the D: drive (while it was on C:), hence uninstallation failed as it was targeting the wrong drive.
As said, installing KKND2 on top of that old installation allowed me to uninstall it correctly. Possibly there would have been some other way to edit some file to make the uninstallation script to target to the right drive, but oh well.
I presume you installed the game manually, and you are not talking about installing or uninstalling it with Galaxy. I can't help you with Galaxy as I don't use it currently.