Are you sure it was Crystal? I observed this behavior in GBA games, where save files are written in flash memory and the battery only serves to run the internal clock. But GB/GBC games use batteries to save the game too, instead of using flash memory, they use RAM, which is constantly kept powered on by the internal batteries, the same batteries that, in GSC also run the internal clock.
...and while typing this I realized how this could be possible in Crystal. There is a small piece on the left side of the cart's circuit, I forgot what it's called, but it basically acts like a metronome, counting seconds while the game is not being played, and the cart uses it for its internal clock. It might have been damaged while replacing the battery.
I replaced the internal batteries in all Gen 1,2 and 3 carts using this procedure: http://victoryroad.net/showthread.php?t=2044 . They are in perfect working condition now, with the internal clock running as it should. I obviously had to start my Gen 1 and 2 save files over though.