I've noticed when removing some products that utilize Microsoft Windows Installer (.msi) that it typically asks for CCleaner to be exited before uninstall can continue.
So how about an option in 'Tools->Uninstall' or just in the general 'Options' area that allows CCleaner to automatically exit when clicking 'Run Uninstaller'?