Easycleaner sucks! I had a similar experience with it years ago- (but not as bad, I didn't need to reformat till a few months later) but I did eventually need to reformat.
I use Crap Cleaner now, but you still have to be careful. It does a good job though.
(first google search)
http://www.filehippo.com/download_ccleaner/