Auto Start project does not Auto Start reliably when published. This appears to be fairly common, especially with newly published project but occasionally happens with republished project as well.
Auto start will start working according to the defined schedule after Symantec Workflow Server service is restarted.
Workflow Solution 8.1
Workflow Solution 8.1 RU1
This issue is fixed in Workflow 8.1 RU2 and newer.
Auto Start will start working properly if services (namely, Symantec Workflow Service) get restarted after publishing the project.