Well, maybe you should sleep on it, come back tomorrow, and the answer might just be looking you in the face.
I remember a couple months ago, I was routing my cables in my case so that they weren't a jumbled mess. Well, I thought I'd go ahead and round the cables while I was at it. I removed the cables, rounded them, and then went to put them back in. Well, I was running a RAID array at the time, so I had to put the IDE cables from the hard drives into the RAID controllers and not the regular IDE connectors. Well...guess what I did... I put the HD cables into the wrong IDE connectors. I sat there for 40 minutes wondering why it couldn't find a RAID array or an OS to boot too... I went to sleep, woke up the next morning, glanced in my case, and immediately realized what I had done. Boy did I feel stupid!!
Edit: Yes the PS looks like it could be it, but you said the same thing happened with two different motherboards being setup and run for the first time with different PS's, so I really don't know. Maybe it's something you did when you put it together.