Did you clear the CMOS after you changed the battery? There is a small jumper that is used to "clear CMOS" by moving the jumper to the clear position and then putting it back where it was. Open your computer and look around your motherboard for a jumper labeled "Clear CMOS". These jumpers are usually located near the BIOS chip itself or near the CMOS battery.
Also make sure your battery is properly seated and is oriented correctly, i.e. not upside down.