Something is wrong with the permissions of the files where Classic Shell is installed or where it creates shortcuts. Try turning on the MSI logging with the /l switch as shown here:
http://www.classicshell.net/faq/#install_commands.
Also, go to C:\ProgramData\Microsoft\Windows\Start Menu\Programs, open that folder's properties and from the Security tab, try giving the SYSTEM group full permissions if it doesn't already have, including replacing all child object permissions. If it fails, do the same for C:\Program Files\Classic Shell\ folder. Give full permissions to SYSTEM group including child objects.
Then try if installation succeeds again.