However I've since ran plenty of reg cleaners so that shouldnt be much a problem anyway.
Well... you've put the finger in the point...
Most probably, registry cleaners messed your system.
They're powerful tools, some does good and save (like CCleaner), some do it very deep and mess everything...