I have this same exact problem on a new HP pentium with a serial (SATA) hard drive.
It looked like the problem might be the drive itself, until you mentioned you got the same problem with a new hard drive.
So maybe something to do with the controller(?).
I wouldn't think bad RAM would corrupt the boot sector, but who knows.
These intermitant problems are hard to fix. Mine may work for 2 weeks, and then crash, with a bad boot sector. Sometimes just fixing the MBR with a bootable utility CD fixes it.
Sometimes the whole drive needs reformatting. But the fact that it's formattable suggests the problem is something else.
None of my other machines does that
One thing that comes to my mind is poor HD cable connection.
I had once a problem like that. It was caused by power failure in a very bad moment. UPS would've prevented that from happening.
You should post more details about your system. Motherboard, HD model and OS being first 3.
Corrupt MBR isn't caused by BIOS boot settings. It can only be caused by some incompatibilities between HD and chipset/motherboard, hardware failure, malicious software or just plain bug in OS.