Hi,
I would not recommend buying a new power supply unless you can pinpoint that as the actual problem or at least be very close to it. The Asus PROBE program on your computer will help you do that. You might want to look here to kind of know what you need and if what you have meets that need:
How to pick the size of a power supply:
http://www.jscustompcs.com/power_supply/
The Prescott chips do run hot and you might like to look at this comparison of chips and heat:
http://www.theinquirer.net/?article=16952
Processor state - Idle/Burn (deg C)
P4 Prescott - 45/61
P4 Northwood - 30/48
P4 Gallatin - 32/51
Last and not least....memory conflicts (even those on the approved list) can also cause what you are having. You might want to take one chip out and see if you still get a random reboot. Also, double check to make sure your memory is on the approved ASUS list for memory for that motherboard.
Gee, I hope you get that darn thing working correctly. Let us know how you are doing and what progress you are making.