Hi JohnPC33, welcome to the forum.
Nothing you've mentioned really screams to me a particular problem, and since the issue is presenting itself prior to booting I wouldn't rule out hardware.
I would firstly make sure to thoroughly check the BIOS for any incorrect boot settings.
Starting note - When trying to troubleshoot a PC be sure to take note of even small changes and/or patterns that crop up during your testing and when powering on/off etc. This will help narrow the problem down. Stop and report back here if you notice anything new.
1. By changing the CMOS battery you mean you replaced it with a new one? If not do so first.
2. I'd then run a Memtest on your RAM. Before that though make sure your RAM is properly in place. If the Memtest fails, run it again, but this time with a single stick, in each slot, one by one. Again, if Memtest fails at any point, repeat the process with another stick until you confirm neither a RAM module or a slot is the problem.
Let me know what you discover with this and we'll go from there!