I have many workflows on Redmine and since we started to use it in my company we've been the same problem in some workflows. Here's the thing: when I created one of our workflows, some status that don't belonged to that workflows simply apers there. They're not selected between the workflow's status.
The other problem that I have is that after the last Redmine update when I select a status in my task and save it, Redmine don't save the chosen status. When I open my workflow of a new task created, it shows all the status save on redmine.
About issue #1, on workflow admin page, clear the check "Only display statuses that are used by this tracker" to see if that keeps happening.
About issue#2, I have the same problem here: new issues get workflow changes but old ones not. I've tried making a copy of the old issue but the problem continues.
Update on #2: apparently new issues created AFTER changing the workflow do work right. Old ones not. At least this is what I've just noted. Sorry for the bad news, but I'm not an expert on Redmine, simply a user.