See what the voltage is at the test point for the CMOS - it sounds like you may be losing that voltage. With a meter attached, lightly push or roll each battery and see if you lose the voltage. An analog meter works best, but a digital will work.
Also, look closely at the tabs for the batteries - I've seen those partially break off, and you never get a good, reliable connection to a battery.