Let's add a couple items to be sure it works. First, when you remove the button battery with no power cord attached, also look on the mobo for a set of 3 pins that say "BIOS Reset". Move the jumper on two pins to the other two pins for about 10 sec, then move it back to its "normal" position. THEN replace the button battery and restore power.
This will reset the BIOS. BUT just to be sure it has a good set of parameters to work with, you really should deliberately load in a set. As soon as you power up, go into BIOS Setup and look at one of the last tabs / screens for a place to Load one of several possible configurations. Load the Factory Default or Optimized Default set. Then Save and Exit to finish booting.
As tritinofg said, you will also have to re-set any custom settings you had before once this is up and running.