When changing the workflow, sometimes the content isn't reindexed, which means the new rights are not applied.
This seems to happen when the workflow for a content type is changed.