Gitlab autoscaling: "Failed to request job: runner requestConcurrency meet"

Question

We've set up a Gitlab autoscaling master machine as described in the official docs.

The gitlab-runner instance works, is recognized by gitlab.org, and also successfully spawns runners to execute the jobs.

However, the jobs don't get really started on the spawned runners. They stick at this point.

We have debug-level logging turned on, and the only unhappy-looking messages are these repeated ones:

msg="Failed to request job: runner requestConcurrency meet" 

config.toml looks like this:

concurrent = 20
check_interval = 10
log_level = "debug"
log_format = "text"

[session_server]
  session_timeout = 1800

[[runners]]
  name = "gitlab-runner-master"
  url = "https://gitlab.com/"
  token = "blabla"
  executor = "docker+machine"
  limit = 25
  [runners.custom_build_dir]
  [runners.cache]
    Type = "s3"
    Shared = true
    [runners.cache.s3]
       ServerAddress = "s3.amazonaws.com"
       AccessKey = "blabla"
       SecretKey = "blabla"
       BucketName = "gitlab.cache.dyynamo.net"
       BucketLocation = "us-east-1"
    [runners.cache.gcs]
    [runners.cache.azure]
  [runners.docker]
    tls_verify = false
    image = "amd64/ubuntu:16.04"
    privileged = true
    disable_entrypoint_overwrite = false
    oom_kill_disable = false
    disable_cache = true
    volumes = ["/cache"]
    shm_size = 0
  [runners.machine]
    IdleCount = 0
    IdleTime = 600
    MaxBuilds = 100
    MachineDriver = "amazonec2"
    MachineName = "gitlab-docker-machine-%s"

Any ideas what the problem can be?

Have also noted this still-open similar issue.