If you are sure the new battery was good and it is still giving you this message it maybe a bad checksum value that got corrupted somehow. I would try reflashing the bios if you are sure the battery that you replaced it with is the right voltage and size.
This is more of just an annoyance then a problem so if you can't find a bios to flash it with I would just live with it.
Read somewhere else they were getting the message still after changing the battery and was told to clear the event log in the BIOS and it worked.
I'm having the same problem but I have tried changing the battery yet...just tried clearing the event log...so maybe you have to do both.