I've been having a similiar problem getting CCleaner reloaded on my computer. It's a Compaq Armada 1750 with a 500 MHz Pentium III, 192Mb RAM, and running Win98SE. I've used CCleaner for quite awhile and I've been very happy with it.
In a nutshell, what I ended up doing was uninstalling CCleaner and then used RegSeeker to remove any references to CCleaner. Used the same program to remove anything else it didn't like. Then I grabbed an older version of CCleaner (220.127.116.110) and installed it instead. Now CCleaner is working properly.
At the end of the day, I probably didn't need