I have encountered this before, but cannot remember how I resolved it. I must delete and reimport the workflow, I will.
My start settings are set so that the workflow will run when an item is created. When I create an item, the workflow starts, but it just stalls and says "Starting" and never progresses. I left it overnight and checked the next morning and nothing. When I cancel and start the workflow manually, it starts.
Any ideas what is going on here? Like I said, I encountered this before, but it's been a long time and I can't remember why it happened, where it happened, or how it was resolved.