First, before trying the next steps, try to download the installer of the exact version you have installed and see if can be removed.
See here for installers for older versions:
http://www.classicshell.net/downloads/ If despite running the installer of the version of Classic Shell you have, it can't be uninstalled, then read on. It means that your Classic Shell installation is in a partially installed state. This is a Windows Installer issue (system related). It can happen with any other software that uses Windows Installer, not just Classic Shell, nor something that is caused by Classic Shell, but due to the installation system it uses.
To fix this, there used to be an unsupported tool by Microsoft for cleaning up partially uninstalled Windows Installer-based applications called Windows Installer Cleanup Utility. Download this tool from here:
http://www.softpedia.com/get/Security/Secure-cleaning/Windows-Installer-CleanUp-Utility.shtml , install it and open it.
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 and remove the tool from Programs and Features.
Also, note this tool is recommended only for your convenience. Classic Shell does not bear responsibility for Windows related issues or anything that may happen from the use of third party tools we recommend for troubleshooting.