1. Open CCleaner from Start->Run and manually have it load CCleaner.exe (don't use a shortcut).
2. Go into Options->Advanced and make sure this box is not ticked: Shutdown after cleaning
I was having the same problem, did the first two you suggested and yeahhhhh!! No more problems. Thank you and have a great New Year.