CPU 62°C, heatsink is lukewarm to touch

All right, I've overreacted and spent a lot of money and not fixed my problem, so I need some help.  I've got an AMD Athlon 1600+ CPU, in a mid-tower case, with an ATI 9700 graphics card (extra power supply, fan), one hard drive, and a CDRW and DVD drive.  I've been using this system for over a year, since I replaced a bunch of parts.  The latest addition was the video card, a few months ago.

Last week, right after a fairly long session of Counterstrike, my computer began to run super-slow.  Incredibly slow.  I rebooted, and the windows boot-up took almost 20 minutes (instead of the usual 1.5).  After looking at a few things, I checked the BIOS and found that the CPU temperature was around 67.  I turned it off for an hour, turned it back on, and it ran fine, but the idle temperature was up in the mid 50's.  The powersupply fan seemed slow, so I figured that was the problem.

Now I've got a new, higher quality power supply, a new motherboard, and a second stick of 512Mb ram that I bought to check whether the dust fried my original stick or the memory slot in my original motherboard.  I cleaned the heatsink and fan, cleaned the mating surfaces of the sink and the CPU, and applied Arctic Silver Ceramique, following the directions to the letter.

My CPU is still idling in the high 50s, and I tested it out playing half-life2 in a window and it climbed to 63 in a matter of a few minutes. Speedfan tells me that my CPU fan is at 4400 RPM, and my Powersupply fan is running at 800 RPM.

But what puzzles me is that the heat sink barely feels warm.  Could there be something wrong with the temperature sensor?  Does the Athlon 1600 have a temperature diode, or is the sensor in the MB?  What's my next step?