Based on those symptoms, and if it's having them w/everything at stock, the next thing you should be thinking about is either bad memory, or having shorts in the system. As Foxdie says, next step is logically memtest, or trying other sticks. Unfortunately memory problems typically cause BSOD or freezes rather than full shut-down, but it doesn't hurt to check.
Dumb question here, but when you built the system you didn't forget the motherboard standoffs, did you? Hey, it happens, believe me
Barring that, you are probably going to have to try disconnecting/replacing various components one at a time until you find the one that is faulty. There's no way you're underpowered, and if your old PSU damaged something (which I think is unlikely), you're still stuck with this same basic methodology ... you need to find the part that's causing the problem.
Start w/easiest stuff first ... optical drives and sound card, then HD(s) ... and then you'll have to move on the pita stuff like the gfx card and mobo.
Oh ... one other thing, just to be sure ... try plugging the GPU power cables into the different modular jacks on the back of the PSU. The HX1000 is actually 2 500W units in one box, and it's possible, depending on how you config the modular wiring, to accidentally plug your entire system into just one of the 500W units.Edited by brettjv - 5/11/11 at 1:00am