This one should have slapped me in the face.

Some users couldn’t fire off a workflow, while others could.
The workflow was updating an item and inserting an item in another list.

hmmmm, what could it be?

The insert action of the workflow…. Some users didnt have permissions to the other list.
Updated the permissions, had the users try again, done!