To chime in, yeah, I don't think a 500W unit is a good call. Might work, but spring for a higher wattage unit.
Not just a higher wattage unit, mind you, a solid unit. A 700W unit is probably fine, so long as it's not a lump of crap. Typically, Antec, Corsair, Thermaltake, Silverstone, OCZ, PC Power & Cooling...to name a few are what you want to look for. Don't go cheap, since you tend to start finding some crap like Apevia (a lower wattage unit marketed as a much higher wattage unit and cheap construction).
At the same time, I don't think you need to spring for a 1KW unit. That's over kill unless you intend to add a second 6870 in Crossfire down the line. In your range, I'd look at anything within the 650W to 850W. It's not that you can't go past that, it's more that this becomes excessive for your computing needs.