If its shutting down after a few minutes, also make sure the cooling is sorted out.
Make sure the Heatsink is properly seated with a sensible ammount of gunk.
Clearing the BIOS too, I asusme you did that of course when oyu upped it.
It still does it with a PSU change, and GFX too, so we know its not that.
RAM usually warns us in other ways than shutting the system down, so its doubtful its RAM, however if you have more than one stick, then not testing single sticks out is silly, so have a go.
So, in this 5 minutes or so, it does seem to be running fine?
It does sound like Temps though.
In saying that, I have a Mobo that has suddenly started to develop weirdness and Im still working on why it does that, so who knows?
Ok, have you made sure that all the contacts are firm? ( The power connections to the HD etc )
And is everythign else seated right?
Sometimes when you have been through most of the obvious stuff, simply taking it apart and rebuilding it can help... Sometimes you find a screw wedged where it should not be, or that the board is not seated 100% right on the brass risers or whatever?
Few things to look at anyway.