cmos or bios Pentium II

If I unplug my computer, and then plug it in again, I cannot start up the system when I push the "on" button. If I remove the lithium battery that powers the CMOS and put it back in after a few muniutes, I can push the on button and the computer will turn on. I replaced the battery, but the same occurrence takes place. One of my former IT teacher told me that it may be a bios problem & that I should flash the bios. What are your thoughts on this problem and how can I further troubleshoot to pinpoint what's wrong?

Thanks.