You could start adding your new states to the existing workflow and even start adding transitions from the existing states, just ensure you don't permit anyone to use the transitions until you are ready. Then, if you need to remove some workflow states at the end you may have to lock everyone out as you make those very last changes. [Remember you cannot remove any existing states if you have any files that have used them, so simply remove all transitions going in and out of the states and thrown them in a pile in the bottom corner.]
If you started a new workflow from scratch, at the end you'll need to make a bunch of workflow links from your existing workflow so you can get your existing files into the new workflow when you are ready.
If you are only adding states to an existing workflow, I'd choose the first option. If a significant number of states will be removed, I'd go with the second option.
It is a tough choice...
It seems to me you are saying the States do not need to change. What needs to change are the transitions. They would reverse direction or go from current destination to current source. If this is the case, just right-click the transition and choose copy. Right-click the blank field and choose paste. You will be prompted to choose a new source state then new destination state. Once you have the new transitions going for the proper flow between states, remove the old transitions. By copying the transitions the permissions and notifications are mantained.
You can do this copy/paste with states as well but, like Jeff said, you cannot remove the old states.
Although you often can't delete states - you can rename states. Ideally the renamed state will still make some sense when you look at file history for old stuff. Renaming can help declutter your changed workflow (and your search when you go to search by state).
Importing an exported workflow is pretty easy - right click on the vault (admin tool) and you'll see it. If you export/import it will automatically add "(2)" to the new copy. Better yet export the whole vault (note vault export is not perfect, doesn't bring along Dispatch scripts and a few permissions), then you can try this out in a sandbox vault first.