It is difficult to pinpoint a particuar portion of the mothertboard, which could cause such an error. I would be inclined to doubt a motherboard problem, as it would cause much greater faults in your running OS. (Does it runs OK?)
The boot change is the significant factor. This happens, as you know, before the computer has even begun to look at the software. There are so many possibilities!
But, to which boot device is it defaulting? - Floppy? One thought is that your power supply is beginning to give problems and, in its initial surge, is not giving enough current to the HD to boot up. Once you have changed the boot sequence back again, the power supply has booted several of the motherboard functions and there is less demand on it. Do you have any means of checking the output put from the supply?
I would also go in to the bios and reset everything to the default. This would include any overclocking of the CPU - often the cause of this problem.