How many conditions do you have for start? I've run into cases where with multiple start conditions it takes quite a long time for the WF to start.

Well, several workflows have seen this problem. The most basic has just one start condition, e.g., when field xyz changes to this value then start workflow.   

I was told that if multiple workflows have this same condition, where start condition is based on same field in different workflows, then only the most recently published workflow starts.  That is, the second published, active workflow is ignored. 

Just to confirm terminology: are you going into Workflow Settings, then setting the workflow to trigger on create/change conditionally?  Or are the workflows set to trigger on create/change and you are using a "Run if" action to determine whether to continue processing.

I ask because there are pro's and cons to each.

I typically only use Workflow Settings and conditional triggers if I need to compare the previous value to the saved value - i.e. only run if a certain field changes.  Setting Conditions in Workflow Settings can cause performance issues because all workflows with conditions, simple or complex, are evaluated before the item is saved and the screen released back to the end user.  The more workflows with start conditions or the more complex can greatly increase save time for a user.

If you do not need to compare previous/new values, then simply put a Run if action in, and if it meets the conditions, terminate the workflow.  A much higher probability your workflow will trigger.

Obviously if you go the other route, a workflow start condition, and the condition is not met, the workflow does not fire and will not show up in workflow history.

Note: if you have multiple workflows using the same start condition, can they be combined?

One other note - I have seen where, when I have the workflow status column in a list view, it appears empty, but when I go into workflow history for the item, it has run.  No rhyme or reason, so be sure to check the history to confirm.

It's a pain to have to configure such workarounds because Nintex just doesn't work the way it should. In my opinion this product has ceased to be a viable enterprise solution. That's a shame. I used to be such a big proponent of Nintex products, but at this point I'm just looking forward to moving to another solution.