LoL - just a little metric input here: human body temperature is 98.6F which is 37C. (Kinda helps you get a feel for the temps.)
If your CPU is hot, but 'the fins feel cool', you obviously have poor contact between CPU and cooler.
Clearly the fins should be hot and CPU cool! I could install any cooler I wish, but the stock Intel one is excellent. These Conroe (and Allendale) CPUs run very cool.
The stock cooler has thermal compound pre-installed, note that this works as well as ArcticSilver or whatever but is just a one-time product. Once installed, heated, and then cooled (overnight) it has melted into place and made its seal. However, if you remove the cooler (or even move it slightly which will break the seal) you must start over!
Clean both mating surfaces well and then reinstall with ArcticSilver.
Testing has shown that the very lowest CPU temps come with the OEM cooler compound - ArcticSilver comes very close or equal, but the white crappy compound leads to slightly higher temps.
My E6400 runs 40C and hits ~54C under full load.
With Speedstep enabled (like right now) it runs 1600MHz @ 1.050v with temps in the 30's...
So if your CPU is HOT but
when I feel inside the case, its not warm and the HS doesnt feel hot at all to the touch
...this is not good.
Regards