Remove the CMOS Battery and check for broken contacts in the housing. Also the battery should be mounted with the number away from the M'Board so you can read them. It would also help to check the replacement battery for the correct voltage it should be 3V DC if it's less it's gone flat on the shelf.
There are a few other things that can cause this as well the most likely is that a Jumper has either been removed that allows power to the CMOS or it's been replaced in the [b]Clear Position[/b] stopping any power to the CMOS. To find out what is happening here you'll need the manual that came with the system/M'Board depending on who actually made the computer. If it a Name Brand you can log onto their Web Site and download a copy of the Manual but if it's a White Box you'll need to know the maker of the M'Board which you can get from the BIOS String on the bottom of the POST page it's a long number and letter string and the BIOS name will be listed somewhere on the screen something like Award, AMI Phoenix or the like.
Once you have the BIOS string and makers name you can look up here to find out the Maker and Model number
http://tinyurl.com/nl39d
Once you have the Makers name & model you can then visit their Web Site and download the manual for the M'Board. When you have the manual you'll need to look for the way to [b]Clear the BIOS[/b] this generally consists of changing a jumper from a 12 connection to a 23 connection on a 3 pin header strip. You'll then need to locate this Header Strip and make sure that the jumper is either on or on the correct pins.
If everything is correct and you still have this problem the M'Board is shot and will need replacing. But I think that you'll find either that your replacement battery is flat or the jumper is set wrong.
Col