'New runner. Has not connected yet.' for any gitlab-runner newer than 11.0.2-1

Summary

Cannot use freshly registered runners. They are not picking jobs.

Immediately after running register command:

gitlab-runner register --non-interactive --executor 'shell' --url 'https://gitlab/' --registration-token 'token'

On gitlab page the new runner can be seen as 'New runner. Has not connected yet.':

Running gitlab-runner verify shows all is good, and gitlab shows:

But new jobs are not picked by the runner.

Steps to reproduce

Install any gitlab-runner newer than 11.0.2-1.

yum list gitlab-runner --showduplicates | sort -r
Last metadata expiration check: 0:48:07 ago on Fri 09 Nov 2018 06:28:41 PM UTC.
Installed Packages
gitlab-runner.x86_64               11.4.2-1                runner_gitlab-runner
gitlab-runner.x86_64               11.4.2-1                @runner_gitlab-runner
gitlab-runner.x86_64               11.4.2-1                @runner_gitlab-runner
gitlab-runner.x86_64               11.4.1-1                runner_gitlab-runner
gitlab-runner.x86_64               11.4.0-1                runner_gitlab-runner
gitlab-runner.x86_64               11.3.2-1                runner_gitlab-runner
gitlab-runner.x86_64               11.3.1-1                runner_gitlab-runner
gitlab-runner.x86_64               11.3.0-1                runner_gitlab-runner
gitlab-runner.x86_64               11.2.2-1                runner_gitlab-runner
gitlab-runner.x86_64               11.2.1-1                runner_gitlab-runner
gitlab-runner.x86_64               11.2.0-1                runner_gitlab-runner
gitlab-runner.x86_64               11.1.1-1                runner_gitlab-runner
gitlab-runner.x86_64               11.1.0-1                runner_gitlab-runner
gitlab-runner.x86_64               11.0.2-1                runner_gitlab-runner
gitlab-runner.x86_64               11.0.0-1                runner_gitlab-runner
gitlab-runner.x86_64               10.8.2-1                runner_gitlab-runner
gitlab-runner.x86_64               10.8.0-1                runner_gitlab-runner

Actual behavior

gitlab-runner is not contacting gitlab-server successfully

Expected behavior

gitlab-runner to pick jobs.

Environment description

Latest self-hosted gitlab (v11.4.5)
gitlab runner with shell executor
fedora 28 with 4.16.3-301.fc28.x86_64 kernel