Reg cleaners are EVIL!!! lol
Seriously tho I have never cleaned my reg and I have no problems with my PC, but as mentioned before I do tend to keep my PC pretty clean. If I can be bothered and I uninstall software I will check the reg manually and remove anything left behind.

A couple of people I know use reg cleaners all the time and have never had a problem with any of them, but I just don't trust em I'm afraid...