[naive]

First, I would try opening your case and pointing a large fan right at it, and do some stress testing. If this helps the situation compared to without the fan, it will definitely be a heat issue. You may not need a new heatsink, if you are not overclocking the machine the stock heat sink should be fine. I would try using some new thermal paste between your heat sink and the processor though. I very very strongly urge you to use diamond thermal paste, it transfers heat 5x better than the silver one spartan posted and is nonconductive (less chance you fuck everything up).

http://www.amazon.com/IC-Diamond-Carat- ... B0042IEVD8