Yes you would be fine.
On a side note, that is going to be one sweet rig!
Edit: Although I am not sure that I would buy the cheapest 1000w PSU I could find if I am spending $1k+ on GPUs alone.
Yeah, it should be. The GTX580 consumes less power than the 480 under full load, so you should be okay.