There's a couple oft forgotten settings in Symantec Wofklow Server Windows Service.
If you rt click on the task tray man and pick 'Settings' you'll find a section called "Worfklow Server Configuration"
On the next popup you'll find "Auto Trigger Info" and "Manual Setup Info" back to back.
These two things participate in auto start workflows. Under Auto Trigger Info you'll find the polling interval (default 1440) that the tool uses to actually look for new auto start workflows that haven't been previously found. On restart (as Mr. Rob M) describes, this is run so restarting the Workflow Server service effectively resets this timer and voila, your auto start gets found and registered.
Alternatively you could shrink this auto poll interval OR, add your auto start project to the list of manually triggered projects at which point the auto registration is irrelevant.