However, if I enable the option to start the workflow manually, and do so, the workflow starts!
A google search lead me to an answer:
This behavior occurs because a security fix in Windows SharePoint Services 3.0 SP1 prevents declarative workflows from starting automatically under the system account. After you install Windows SharePoint Services 3.0 SP1, declarative workflows do not start automatically if the following conditions are true:
- The Windows SharePoint Services Web application runs under a user's domain account.
- The user logs in by using this domain account.
- The site displays the user name as System Account.