I presume you've done all the usual permissions tests? The user trying to run the Start Workflow action has required permissions to start workflow 2 as well?
There's no other instance of the workflow running on the item?
There's no pending updates on the item you're attempting to start workflow 2 on is there?
I agree. Check the list of allowed actions in Central Administration -> Nintex Workflow Management -> Allowed Actions. Is everything ticked there?
If so, please check again in Site Settings of the site your workflow is running in.
I've seen this before where item level permissions have been changed for the initiator part way through the workflow before the start a workflow action is used. Like Ryan says does the user actually have permissions or is the action run as a different account? X
What if you tried putting the action that is erroring inside of an Action Set and ran that action as the workflow designer (who'd I assume would have great permissions). Just a thought!