I think @scottvonduhn may have discussed in the past that that error actually means that the user does not have a high enough permission on the record type the workflow is operating on.

Yes, what happened to us previously is that we had some workflows for a custom record that RSM created for us. We had to give myself and our business analyst full permissions on the custom record in order to even view the workflows for it.