Just to update you guys on this little situation...
I got the new memory but had the same issue, got an alternate power supply to try and also had the same issue. After consulting with Gigabyte, I was advised to go ahead and RMA the board defective.
I got the replacement board today and....same behavior.
After consulting with Gigabyte once again, the second technician said that the RMA was unnecessary and that this power cycling is almost always a memory issue but as the memory controller is on-board with the processor, a defect in the processor can cause this as well.
After calling around, nobody local is in a position to test the one I have, so I'm going to go ahead and see what happens when I get the new processor.
I'm a week off-schedule and in for about $30 more than I'd intended in restocking/shipping, but it could be a lot worse. Just looking forward to getting this thing running.
One more problem, mind you, and I'm ordering an Asus.