The CPU in question is an Intel E8400 Wolfdale 3.0 GHz Dual Core. It is running in a headless Ubuntu environment and idles at around 44-53 degrees C and under a load, it jumps to about 90. Eventually, the system shutdown.
I removed the CPU fan (stock, came with the CPU), blasted it with some compressed air, and then blasted various other places in the computer. This has not helped.
Anyone have any ideas?