[This post is not meant to be an exhaustive treatise on this multi-faceted topic.]

If your SharePoint workflows run fine until you apply some kind of SharePoint update to the farm and then proceed to get stuck in a "starting state" (rather than "In Progress"), I have a couple suggestions to offer.  

First, check to see if one or both of the following conditions are true:

•There is a required column with no default value. The workflow starts before the Edit Properties window appears to enter a value for the required column.

•The "Require documents to be checked out before they can be edited" option is enabled.  

Try unchecking “require checkout to edit” from the list (or document library as the case may be) for the affected workflow.  If you can then run the workflow successfully after that such that the workflow status changes to “In Progress.”

If this fits your scenario, probably the best thing to do at this point would be to start a support case with the Microsoft SharePoint team.  Here's a good starting point for that: http://support.microsoft.com/ph/935/en-us.

Updating to the June 2013 CU or higher (I'd recommend the SharePoint 2010 Service Pack 2 instead of the June 2013 CU) will probably help.

 

 

Also see: http://social.technet.microsoft.com/Forums/en-US/sharepointadminprevious/thread/5a6e6e83-b59f-4099-a86f-a07723ff2b98/

Additional search terms: Workflow work items was processed by timer job more than 5 times which means that it is stuck or took too long to complete.  Processing Root Cause: RC_SPWorkflowWorkItemStuck Nintex workflow broken workflow stuck workflow stopped work flow broken work flow stuck work flow  stopped