I had the same problem with the "Overclocking Failed!" message on my P4S800D-X and updated the BIOS to the latest beta: 1006.002 (build date is from June 2006, which is much newer than the 1005 release). Also, make sure to clear the CMOS with the jumper after flashing the BIOS.
http://dlsvr01.asus.com/pub/ASUS/mb/...x/1006-002.zip
Scott