Asus P6X58D-E please enter setup to recover bios setting

So you are saying that the BIOS settings that you set won't stick? Will it remember it's real time clock (RTC) (the date/time) when you set it? When you removed the battery did you wait a little while before putting the new one back in? Either way, it doesn't sound good. What preceded this?

The BIOS stores its RTC and settings data in separate onboard ram that the battery keeps up during power loss. If that ram fails you might get symptoms such as this. I'm not sure whether the motherboard's self test would detect such an issue 100% of the time. I'm not saying that's what it is, just speculating.

If you can enter the BIOS then it's not as bad.

1 -- After a Clear CMOS:
BIOS:
F5 to Load Defaults
Set the Date & Time
/other BIOS settings as needed i.e. SATA -> AHCI if used
F10 to Save & Exit = Yes

2 -- Proper Clear CMOS Procedure:
Your MOBO has a Clear CMOS button @ the rear of the MOBO's I/O next to the purple PS/2. Most folks don't Clear the CMOS properly, Unplug the PSU for ~5 minutes, Press and Hold the Clear CMOS button for 5~10 seconds then let go, plug in the PSU. See -> http://www.youtube.com/watch?v=rdHH9KrceR0
BIOS:
F5 to Load Defaults
Set the Date & Time
Set the Date & Time
/other BIOS settings as needed i.e. SATA -> AHCI if used
F10 to Save & Exit = Yes

3 -- Updating the BIOS -- only use ASUS EZ Flash 2!!!:
Only use ASUS EZ Flash 2, using a FAT32 Flash Drive unzip and extract the (.ROM) file, use only black USB 2.0 ports, press ALT + F2 (if needed the F Lock key), and update the BIOS. See -> http://www.tomshardware.com/forum/289507-30-what-flash

4 -- BIOS Recovery:
If your BIOS is toast and you cannot enter the BIOS:
ASUS CrashFree BIOS 3 - http://www.youtube.com/watch?v=LirQ-oM9XBI
RENAME BIOS = P6X58DE.ROM
<or> use the ASUS DVD that came with the MOBO it already has the shipping BIOS on it.

When I set the time and date in windows, it will remember it in bios.

I took the battery out for 5 seconds. The CMOS clear button at the back of the mobo doesn't seem to do anything.

If the (4) item I posted above fails then if possible uninstall ANY BIOS invasive application e.g. AI Suite and the following
BIOS:
F5 to Load Defaults
Set the Date & Time ; if needed seems not
/other BIOS settings as needed i.e. SATA -> AHCI if used
F10 to Save & Exit = Yes

Reboot & Test

If the problem continues then you have a bad BIOS chip. Contact ASUS and RMA if possible replacement BIOS EPROM chip (if user replaceable).

I tried the asus EZ update, issue still persists. I doubt it is the bios chip as it saves the date and time, just nothing else. Strange. I removed Vtuner, still persists. The board is refurbished by asus themselves so I'm sure It can be fixed here. Any other suggestions?

Try booting in Windows Safe Mode - http://windows.microsoft.com/en-us/windows7/Start-your-...

Why?
I can boot into windows by pressing F2 when the error appears. I want to change some bios settings but they don't save...

I am still thinking you 'might' have some application modifying the BIOS and the Safe Mode followed by a reboot is to see if that's a possibility. Alternative to Safe Mode is to run MSCONFIG and select Diagnostic and reboot a few times.

Otherwise, chances are it's the MOBO.

Q - What exactly are you seeing on the post screen?
Q - Are there any Applications that are installed that can modify the BIOS settings? e.g. AI Suite

Keep in mind those type applications don't need to be in your 'face' to be running, they load in the background.

It's easy for me to say RMA your MOBO -- and if you want what you think is easy then RMA...to me that's a bigger PITA.

Great, the safe mode trick fixed the problem. Thanks

How can I award you as the answer?

Not necessary, and glad to hear you're good! Beats the crap out of an RMA!  

Lol, thanks again.