I know this is a kind of dumb question, but the coin cell you put in, is it A) the right type (many different coin cells) and B) Good?

Your loss of CMOS settings is indicative of low or dead CMOS Batteries. The only other possibility is that you have a jumper set to clear CMOS everytime you boot (not a reset like Ctrl-Alt-Del or Reboot from Saving CMOS but from a Hard or Cold boot)