Thats unreal. How can that not solve the problem, its removing exactly why its hanging. (Don't answer me it was a rhetorical mutter)
Are you sure you did all the reboots etc...?
What about this...
1) Run disk defrag first. Then try cleanup.
or
1) Go to My Computer and right click on the C: Drive
2) Go to properties
3) Make sure that the "COMPRESS DRIVE TO SAVE DISK SPACE" is unticked.
or
1) Run regedit, move to the top of the hives (to My Computer) Press Ctrl-F (Find) and type "Compress Old" (no quotes) When regedit finds the offending key (its highlighted blue), press the Delete key and Enter.
GOod luck
