After much surfing I eventually found a post on one of the MSDN managed newsgroups about my queue problem.
The essence of the post was as follows.....

  1. This happens because on restart the Queue service starts before the SQL Server Service because I am running everything on one machine
  2. There are 3 methods to make this work,
    1. Restart the queue service each time after a reboot (annoying)
    2. Add a dependency via the registry so that the Queue service depends on the SQL Server Service (this works really well)
    3. Ensure that you run SQL Server on a different machine (which you should do in any production system anyway)

To change the registry to create the dependency do the following....

  1. Use Regedit and browse to the key HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\ProjectQueueService
  2. Create a new Multi-String Value called DependOnService
  3. Make it's value MSSQL$OFFICESERVERS or the approrpiate name of your SQL Server instance
now have fun!