I had something kiind of similar once, where it would only boot after trying to boot once, letting it run a bit in idle, and then rebooting where it would actually succeed. Turned out I forgot to put the clear cmos jumper back to neutral after i reset cmos.

So my best guess (other than new battery) is check the jumpers maybe