EDIT: Sorry K I didnt see your reply

Use this is you still have problems after following K's suggestion.
You could try resetting the permissions on all reg keys using SubInACL and allow full control to Admin and System.
Download and install SubInACL from
HereWhich installs into this folder:
C:\Program Files\Windows Resource Kits\Tools
Open Notepad and save the contents of the code box into it
CODE
subinacl /subkeyreg HKEY_LOCAL_MACHINE /grant=administrators=f
subinacl /subkeyreg HKEY_CURRENT_USER /grant=administrators=f
subinacl /subkeyreg HKEY_CLASSES_ROOT /grant=administrators=f
subinacl /subdirectories %SystemDrive% /grant=administrators=f
subinacl /subkeyreg HKEY_LOCAL_MACHINE /grant=system=f
subinacl /subkeyreg HKEY_CURRENT_USER /grant=system=f
subinacl /subkeyreg HKEY_CLASSES_ROOT /grant=system=f
subinacl /subdirectories %SystemDrive% /grant=system=f
Goto
File on the top bar of Notepad and then choose
Save As, change the
Save As Type to
All Files and call it reset.cmd then save it into the 'Tools' folder so its in the same folder as SubInACL.
C:\Program Files\Windows Resource Kits\Tools
Next goto Start > Run > type
cmd press enter then type these commands and press enter after each one.
cd "C:\Progra~1\Windows Resource Kits\Tools" reset.cmd It will take awhile to reset them all then reboot and try Ccleaner again
Andy