Resolution:
When using Services with Task Discriminators, tasks do not get assigned to any Engines, even though there are Engines available to take them. This typically only happens when there are a small ( < 10 ) number of Engines.

There is an issue in version 3.1.1 that results in this behaviour. Specifically, the scheduler does not look at Task Discriminators when making assignments, so an Engine may get scheduled a Service from which it cannot actually take a task. Workaround: If possible, use a JobDiscriminator. Otherwise, ugrade to Service Pack 8.