The documentation says, that you can delete a step from a workflow has no incomming transistions. There seems to be another restriction. The workflow itself must be inactive. At least I was not able the delete a step from an active workflow, only from an inactive.

Please add this restriction to Deleting a step at http://confluence.atlassian.com/x/YAISCw