Have you reset the cmos to defaults after changing the battery? It's very rare, but they can act funky when the voltage droops, but doesn't dip enough for it to fully lose the contents.
Also is that machine new enough to have an SOC reset hole? try holding that for 30 seconds if so. That fixes all sorts of issues that makes 0 science to me.