You mentioned it was a new rig, have you flashed the bios to the most recent version?
This kind of problem can happen if you use the stock bios. I had a similar problem before, the culprit turned out to be a semi-busted gpu. Probably not the case for you, but failing the bios -try that.
Try removing the factory overclock on the GPU, I have a felling about that.