Found this gem on the cheeseshop: Fabric 0.0.3. The original blog post by the author outlining the why and wherefore is here. I have about four or five tools like this I use at work, mostly home-rolled, seeing something like this out and in the open is great, and the fact he used paramiko as a back-end is great.
Maybe it's time to switch out my various little tools and move to this.