Thanks for all the responses guys. Yes, it turned out that the PSU was faulty (750W, was giving much less than that) - I replaced it and everything works perfectly. Thanks again.
What did you replace it with? It's not so much the Watts the PSU can provide but the Amps available on the 12v rail. You shouldn't use a PSU with multiple 12v rails, which is a sign of cheap production, because the Amps available on each is very small and cannot be shared. With a single rail the entire capacity of the PSU is available to all devices connected (There are exceptions to this, with some using multiple rails that can provide over 70amps on each). My system is running the Corsair 950Watt-TX which is giving me 75Amps on the 12v rail, of which both 5970's draw a total of 69Amps.
There are cheap 1000 and even 1200&1500 Watt PSU's out there that have silly amp ratings of around 25 on each rail, with 2-4 rails per PSU. It's these devices that trap first time builders of large systems and usually give the symptoms you had.
Well, I guess I'll agree that a dual 5970 owner would probably benefit from a single +12V rail style PSU to simplify selecting a PSU that will work, but multiple +12V rails doesn't necessarily mean that the power supply is produced cheaply. 25A at 12V is 300W, by the way. PCI express standards published by PCI-SIG specify that a single PCI express device
should not exceed 225W external power plus 75W bus power (300W total). The 5970 at stock clocks falls within this standard, so even a 25A rail by itself could feed this card just fine, typically only needing to feed it 19A anyway. I underline should not because as the 6990 (and almost definately the upcoming GTX 590) shows that AMD and nVidia don't really care about an established standard. Even at 375W, a PCI express rail going into one of these cards need only provide 25A (but should probably be rated 30A).
Your 5970's draw (roughly) 828W of power? Does that mean you're running something like 950 MHz on all 4 cores? If they are drawing that much power and the card is connected by the default 8-pin + 6-pin power plugs, I'd worry more about your solder joints.