The message is misleading; it means you need higher permissions on the record type to which the Workflow is deployed.

Nice one @erictgrubaugh! That worked. Thanks a lot.