Personally, I stay away from registry repairs/cleaners. Many of them seem to be a bit less than helpful. However,
CCleaner is a great program. Just make sure you install it without the optional Yahoo! toolbar, then use CCleaner to clean out your temp files and registry (be sure to make a backup when prompted).
Try running a scan with
SUPERAntiSpyware in Safe Mode. If you are still experiencing problems, feel free to post a new HijackThis log so we can see if something else might be lurking about.