It sure sounds like a heat related problem.... Between the heatsink and the processor should be a thin coating of thermal grease/compound.. If you didn't apply new thermal compound after the cleaning, you'll need to do it now..

Hope this helps.

Grif