Hi I have the same problem more or less, according to intel's website the thermal spec for my 3.00Ghz Prescott P4 is 69.1 C. I have not tinkered with the settings nor overclocked this P4 it just seems to run hot.
When idle my CPU temp is about 59-64C however when running games or some other applications it jumps to around 74-78C, but my system temperature remains at a nice 27C.
These temperature fluctuations were occuring with the stock heatsink and fan installed which should have been able to cope, but obviously couldn't so just to test I went out and bought a Cooler Master D14-8KD3B-0L heatsink and fan, for P4's 3.6GHz or higher...
Sadly it has made no difference whatsoever and I am concerned for the health of my PC.

Those temps seem fine.
Tt Lanfire
MSI K8N Diamond
AMD64 3000+
1gb pc3200
OCZ Powerstream 520w
6600GT
WDCaviar 160gb sata
WDCaviar 160gb sata;~}
thoses temps are high i have a prescot core its a intel celeron 325, runs ok at idle it runs around 31c, at full load it runs 36c-39c...how fast rpm is ur cpu fan runing usually my cpu fan is runing around 1960 rpm. Presscot @ 2.5g
2x256mb Samsung
Pny geforce 6 6600 GT
40gb seagate HDD
i845GE
The temps you're seeing are not uncommon for a Prescott. Have a look at this thread & take the time to read Lazyman's reviews...he's done a LOT of work with the Prescott: http://www.computing.net/hardware/wwwboard/forum/35256.html
Asus A7N8X-X
1800+ @ 8.5 x 200MHz
768MB PC3200
Asus A9550 128MB/128-bit
Gamer Edition
WinME/WinXP Pro
Ya know, it's not a good idea to compare a Celeron 325 to a 3Ghz P4E. Both may be built on the Prescott core but that's where the similarity ends. A couple of links;
http://www.madshrimps.be/?action=getarticle&number=1&artpage=867&articID=225
This is a case review but the info you'll be interested in starts on about page 5. It's a 2.8 P4E oc'd to about 3.5Ghz.
A bunch of hsf's compared;
http://www.madshrimps.be/?action=getarticle&articID=245
and
http://www.madshrimps.be/?action=getarticle&articID=245
Long reads, but worth the time.
Skip
the big question is...the temp the bios or software is reading, is it accurate? do the "touch" test.... touch the base of the heatsink...if it really is 60 at idle, it will be very hot to the touch, if barely warm to the touch at idle, then it has to be a temp reporting problem 60 at idle is kinda high..i idle at 40 in an overclocked condition and load at 60
DFI lanparty 875p-t LGA775 2.8 @ 3.5
2 x 512 Geil Ultra Platinum PC4000 @ DDR500
128 meg Radeon 9800 Pro
DUAL 36 GIG WD Raptors RAID0
21 in. 19.8 viewable Sony Trinitron
4 Mbps cable
