BIOS keeps resetting my CPU's clock speed?

First of all, I don't really know what info is needed or not needed to help me, so forgive me if I leave something out.

My computer:
AMD X2 3600+
Biostar T-Series 550 motherboard
2x 1 Gig PC6400 800Mhz RAM (I forget the brand)

I decided to overclock my CPU. I'm only using the default heatsink/fan, but there are plenty of reports on the internet of 75%+ overclocks with my exact CPU/mobo combo on stock cooling. It runs at <30c idle and 60c at full load.

The stock speed is 200Mhz bus with a 9.5 multiplier. Yesterday I ran stable for several hours of gaming overclocked to 250Mhz; no problems whatsoever. However, after resetting the computer, it started back up at stock speed. Even going into the BIOS and changing it again doesn't fix it. I don't think this is temperature related, since it will do it even from a cold boot, when the CPU is <25c.

The bus speed was the ONLY thing I changed in the BIOS. The CPU voltage is set to auto, which puts it at ~1.3V. Manually upping it to 1.4V doesn't help. I'm reasonably certain that the bus:RAM ratio is set to 1:1.

Any ideas? Any help is appreciated!

If the CMOS battery is dead, would that mean it can't save any settings? Because I made some minor changes to remove logos etc, and those worked just fine.

That seems a bit drastic...are there any other explanations than an out of date BIOS?

Did you review your manual thoroughly? It appears that there are couple of overclocking tools in your BIOS, manual and automatic. It also says the the board will automatically reset the BIOS to default at boot if the overclock settings are detected as unstable. Did you unlink the memory? That is usually the first thing that will kill an overclock, running the memory out of spec. Make sure when you overclock the buss, you select a mulitplier that keeps the memory at or below stock speed.
The reivews I have read on this board do describe it as an overclocking demon, and the BIOS rivals that of DFI. If that is so, the DFI BIOS's can be pretty overwhelming with all the settings. Just requires patience, and a lot of trial and error.
But check on the memory thing first, then go from there.