A good 650w PSU will run 2 5870s at stock clocks and a Sempron. Of course, if you are using a CPU above a Sempron or overclocking you might want to go with 700w or 750w.
+1
I'm running a pair of 170W cards and an overclocked Core i7 950 on a 700W power supply just fine. Any 1000W power supply that follows the ATX spec will run a pair of 5870s at whatever overclock they can feasibly run at as well as all of the other components in your system, but you would've been fine using an 850W PSU as well. I'm sure that 1000W unit you got will be more than enough.