Nintex Workflow stuck in “Starting” state

If you find your Nintex workflow never leaving the "Starting" state, set the value in the Form Library settings:  ‘Require documents to be checked out before they can be edited’, to “No”.  This is a known Nintex bug:  http://connect.nintex.com/forums/thread/29961.aspx