That cooler is a 92mm fan based cooler. It should have a fan on it. I have seen stock get that hot and hotter.
One thing I notice is that your turbo is locking in full bore even with all 4 cores loaded, this is the motherboard doing that. So it will get a bit hotter in general, you would only get 3.7 with 1 core and the speed lowers as all cores are loaded.
Now it is important to know not everyone reads the temperatures the same way. Many users reply on the motherboard software(a sensor in the cpu socket area, may users with 15c idles and such post this temperature). This in many cases gives a lower temperature then lets say CoreTemp(a sensor built into the cpu, one that is also less accurate at low temperatures as it is made to trigger the thermal protection more then anything).
My media center shows about 7-10c higher with coretemp/hwmon then the motherboard software. I have even seen the motherboard software show 17c in a 20c room.
YES 72 is a bit hot(i would not think cpu damage hot yet), but may programs will NOT work the system that hard. Intels temperatures are listed as the top center of the heat spreader(so a good 10c cooler then what a core temp would show up as).
I would guess you used a 92mm fan based heatsink because of space limits? If not, the posters who recommend a CoolerMaster 212+ or EVO are quite right, that heatsink packs some real performance under $30 in most cases.