We found a solution to that inadvertently when we set up our Deal status - to get the "alphabetic sort" to sort our stages in order, we named them "1 Prospect" "2 Pre-contract" "3 Contract".  We can add new stages by adding decimal numbers: "1.5 Demo", for example.  It doesn't completely address your issue.  When we did change our stages, I simply tagged the Deals in each stage with a tag for the stage, deleted the stage, created the new one, then clicked on the tag and batch added them to the stage (and deleted the tag).  It took about 5 minutes and worked perfectly.

gfisher - that is an awesome work around to this!  Thank you for posting that!