What's the voltage of the new cell? Was it a good cell or could it have been already half dead? If the motherboard keeps eating batteries then it may be drawing too much current. Corrosion on the board?
On the other hand, if the cells, both old and new, are good, then you may have a bad CMOS memory chip that fails the check.