bargainhunter

I have been playing with my game boy advance for the past few weeks and I've never had any problem with saving scores and data. But today, after replacing my battery, all the data that I haved saved were gone (particularly with my gameboy color games like supermario dx, magical tetris challenge, mario tennis). Is this supposed to happen everytime you change battery, or is there a problem with my unit. I guess compatibility has nothing to do with it since GBA is supposedly backward compatible. I also noticed that starting today, whenever I would remove the game cartridge and replace it, the data would be erased. Is there something that I should know regarding saving data?