As a last resort, you can try downloading Windows Installer Cleanup Utility from here:
http://www.softpedia.com/get/Security/S ... lity.shtml Note that you must install and run Windows Installer Cleanup Utility as administrator (with elevated rights).Be careful with the use of this tool. It should list all applications on your system which use Windows Installer including some version of Classic Shell. Select Classic Shell in that list (and make sure you don't select any other product) and click "Remove". Let it remove and then click Exit.
Now try installing the latest version of Classic Shell and it should work. If no version of Classic Shell appears in Windows Installer Cleanup utility, exit the tool without doing anything.
Actually since you have already tried the Classic Shell Utility to cleanup, Classic Shell shouldn't even be listed in the Windows Installer Cleanup Utility, but it's worth trying since somehow your system still says it is installed. WICU should clean up any cached MSIs from %windir%\Installer folder which might be preventing you from reinstalling/repairing Classic Shell.