It should NOT be a problem of "having enough power" A friend of mine runs a 8800ultra on a nearly identical PSU to mine; antec TRUE480(mine is trueblue480). Here is his rig;

CPU: Athlon64 2700+ (one of the first socket 754 CPUs)
vid: BFG 8800 ULTRA this
HD: 7 ATA100 80GB maxtor drives
mobo; forgot which model but its basicaly a normal socket 754 mob, only with PCI-express slots
mem: 1GB DDR400
PSU: antec True480

He says it runs just fine, and I checked the voltages on it while he was playing Bioshock and they were the same as when he booted so the powersupply is probably fine with the full load of that system.

All that being said; Chances are its not your PSU. If you want to be sure check your PSU in another computer and see if it works.

Edit; not sure if antec still holds up to this, but back in the day(2001) when a powersupply was labeled TRUE### the ### wattage was what it could output up to continuously without any problems. Nearly every powersupply maker nowadays label PSUs based off their peak output. You might want to make sure your PSU can is not like a 500 watt continous, 850 watt peak.