Make sure all your cables are bundled as nicely as possible, and away from any fans. I'm assuming by cleaning, you mean you sprayed out all the dust with air. The next step if you're still having problems, is to apply new thermal grease to your cpu.
First you'll have to take off your heatsink. If you don't know how to do this, tell me what type of processor you have, and I can help.
Next, remove the old thermal grease. I use a q-tip and isopropyl alcohol to clean off the cpu. Then clean off the rest of the paste from the heatsink (scrape it off with a utility knife, and then use the alcohol).
Then place a small drop of the thermal grease on the processor. Don't worry about spreading it out, as it will spread out evenly once you put the heatsink back on. Also, don't put too much on.
Put your old heatsink back on (or buy a new, better one if you're running stock) and see if that helps.
If you've tried overclocking at all, put everything back to default. It's not worth frying your computer over a minuscule amount of gain. If you really want or need the better performance, buy a better processor.