This typically indicates a corrupt BIOS. This issue then becomes, how did it become corrupt? And why didn't it sort itself out when you replaced the battery (as that action resets the BIOS)?
I don't see any updated BIOS versions at Gateway
. Otherwise, I would suggest flashing the BIOS. I think you should reset the BIOS again. Disconnect all unnecessary attached devices (drives, USB devices other than mouse and keyboard, etc.), then unplug the computer from the wall to ensure all stand-by voltages are removed. Open the side panel of the case, touch bare metal of the case interior to discharge any static in your body, then pull the CMOS battery.
If the replacement was not a new battery, go get a new one. Though rare, new batteries can be bad right out of the package so consider replacing with another new one, even if you just put in a new battery.
Do NOT touch the replacement battery with your bare fingers - skin oils promote corrosion and attract dust. I put a clean cotton sock over my hand. While inside the case, inspect for dust build-up and clean as necessary. Then inspect to ensure all cable connections are tight and secure, and cables are routed and tied back to minimize impacting the desired front-to-back flow of cool air through the case.
Then connect power and upon first boot, boot into the BIOS Setup menu. Set/check date and time again, and ensure drive boot order is correct, then "Save
and Exit" to [hopefully] boot with no errors. If you do not "Save
and Exit", you WILL keep getting these errors.
If that does not resolve this problem, then I fear your motherboard is failing.
You can try flashing the BIOS again using the BIOS from the utilities disk that came with your computer, but I don't hold much hope in that, I am sorry to say.
When it does finally boot, does it see all your RAM? Any errors in Device Manager?