[KarmaKiller]

Ok, well that's a good PSU, so I have a hard time thinking that's it. But I need to check to see if the 750w is required to run both GPU's on the card, or two cards.
As far as the BIOS update. I think this could be considered a last resort thing. But in general, a BIOS update is a good thing. BUT, you have to be careful while doing them. Read the instructions!! There is a chance if something were to happen, that you could brick your board.
But if your follow the instructions, you'll be fine. Also, if your OC'd at all, make sure you set it to default settings.

Do the BIOS update, then see what happens.