When you replace a battery, you should always clear the CMOS using the jumper on the motherboard. Ensure the jumper hasn't accidentally been put on the wrong pins. Make sure you look at all the important settings afterwards, especially any that you have set differently to the default settings.
It's always worth changing the battery again - just in case - and because further actions will be likely much more expensive/difficult.
If you can identify the CMOS chip (in the manual usually) - and it's in a socket (many will be) - then try pressing the chip into the socket - they can creep out of the socket under continual heating/cooling cycles.
The last two actions are much more drastic - reflash the chip - then change the motherboard - there's not much else you can do.