If I'm reading you correctly, sometimes when you boot the system, it works properly, and sometimes it fails right away with the disk boot failure. Aka it's never partially booting and THEN failing.
Narrows it down quite a bit. The failure I just indicated is caused by the system not spotting the disk properly at boot time.
It can be caused by... disk not finishing its internal boot process properly in time for the system boot, so the system doesn't spot it.
Bad cables (you'd probably have more than just the symptoms you mentioned though, even with just an intermittent cabling problem. note: key symptom for this would be drives dropping out of the chain while the OS is running... if it was the system disk, your system would lock up at this point)
Disk controller starting to go on the fritz (built into the chipset... how old is your motherboard? see also notes for cabling)
Ram problems. Yes, believe it or not. The good news is, easy as pie to test. And free.
Disk corruption. (less likely... you'd be exhibiting more problems than just what you mentioned)
Probably some other stuff goes here. I'm tired.
Ok, easy way to start. Assuming a: you have a bootable optical drive in your computer, and b: that you you have an optical burner installed in at least one computer in the house. These are pretty reasonable assumptions.
Go here.
http://memtest.org/Download, and burn a copy to disk. Make sure you have a valid copy, etc.
Stick disk in bootable optical drive. Reboot to the cdrom. It's fully automated. Let it do its thing, preferably overnight, when you have the time. If it finds problems, then you get to have fun.
Also, keep the disk handy. Wait for your error, then when it asks for a system disk, stick the cd in the bootable cdrom, and see if it boots from it at that point. (if it does NOT, that lends more credence to the drive controller being an issue).
If the memory scan finds errors, at that point, you need to power down the system, pull all the memory dimms except one, mark them a, b, c, d, and test them one at a time until you find the one giving you problems. If you get to this point, and can't get one of them to 'give it up' so to speak, don't sweat. The simple process of unplugging and re-plugging memory dimms, sometimes fixes the cause of the problem.. aka dirty contacts.
Get back to us and update this thread

Atomic
PS: When you have the disk boot failure symptom, if you warm restart, aka without powering down, by hitting the reset button or cntrl-alt-delete if it's working at that point, does it then start up without issue? That makes me look more at the disk being the problem. (my comment earlier about the disk not finishing it's internal boot process in time would be relevant here)