Check the memory of your farm. Also check your log files to ensure you don't have something funny happening there. Those are the two things I've seen affect it.
Also check that your workflow are not too big!
There can be issues around publishing large workflows. We were told, if possible to limit the workflow to be under 1MB when exported. If the requirements for the workflow are going to drive this significantly up, the recommendation is to implenet multiple linked workflows to modularise the flow.