You are referring to the CMOS battery and not the main battery, correct? Did it take care of the "set clock" message? If the set system clock message is still appearing, I'll suggest trying a different battery for the CMOS since, at a minimum, that message should go away once the clock is set with a fresh battery - either that or your BIOS is corrupted, let's hope that isn't the case here