I have the same problem, cleanup getting stuck either while scanning for things to clean up or at the clean up stage itself.
Today it identified a total of 25MB of stuff for cleaning, but got stuck at the clean up stage. I tried using the Windows 8.1 disk clean up administrative tool instead, it identified 25MB to clean and cleaned it all up fine.
Best regards
Graham