Red Hat 3scale APIcast returns HTTP 404 (Not Found) with "service not found" in the logs

Issue

When attempting to get an Access Token I get a failure:

[05/Jun/2017:18:07:01 +0000] host.domain.com:12345 10.0.1.2:12345 "GET /path/to/endpoint?user_key=1234567890 HTTP/1.1" 404 5 (0.568) 0
2017/06/05 18:10:00 [warn] 28#28: *100 [lua] proxy.lua:102: find_service(): service not found for host host.domain.com, client: 10.0.1.2, server: _, request: "GET /path/to/endpoint HTTP/1.1", host: "host.domain.com"
2017/06/05 18:10:00 [warn] 28#28: *100 [lua] proxy.lua:76: error_service_not_found(): could not find service for host: host.domain.com, client: 10.0.1.2, server: _, request: "GET /path/to/endpoint HTTP/1.1", host: "host.domain.com"