My 2 cents, replace the CPU. If its in the 30 day return, do it now. If its outside of that start with Intel's Live tech chat. Have your components info with you, specifically board & memory model numbers.
I had this very same problem with a GA-P67A-UD3 board and after a replacement board seemed to make the problem worse I opted for the buy back from NewEgg until the B3 boards were out.
My problem was: reboot during any OS install, reboot during any flash attempt (dos flash), reboot before POST completion and finally reboot cycling before bios could be loaded, before video could be enabled.
I ended up going with an Asus P67 Evo once the B3 boards were hitting the shelves, partly due to another build using an Asus board, and partly due to fear I was going to have another issue with the Gigabyte (their tech support wasn't supportive). Assembled everything on top of a box and I have the same damned problem.
Only the Evo board has helpful LED's that indicate where the board is having an issue, CPU, Memory, PSU. And the Memory LED was steady on. So now I've swapped out memory, again, to a verified QVL module and no change. At this point in the game I"ve replaced everything except CPU. Got online with Intel's Live Chat, suspecting the CPU is bad but really hoping that they'll tell me its a hardware mismatch. In less than 5 minutes I have a ticket number to get a replacement CPU. Next day on the phone to complete that ticket and the following week I have a working system.
The ease in which the tech at Intel concluded the CPU was bad was surprising. He basically asked me 3 or 4 questions about hardware, setup, ect and issued the replacement ticket number, which leads me to think there's an internal bulletin concerning this problem.
It will mimic a memory fault and I suppose it is a memory fault, but not with the DDR memory but the cpu's pathways to that memory.
Date of original order: Jan 17
Date of working, stable system April 14
Number of components used: 3 motherboard, 3 power supplies, 3 memory module sets (all 1.5v), 3 video cards