Fresh install: 401 Unauthorized in check script

I have install gitlab losely following the ArchWiki page (https://wiki.archlinux.org/index.php/gitlab). Neither sidekiq, nor unicorn or workhorse have errors starting up.

When I run the check script, it comes up with

Running /usr/share/webapps/gitlab-shell/bin/check Check GitLab API access: FAILED. code: 401 gitlab-shell self-check failed

and at the same time in gitlab-shell.log:

API call <GET http://localhost:8080/api/v3/internal/check> failed: 401 => <{"message":"401 Unauthorized"}>.

Other than that, no further errors. I have double-checked every configuration file about 200 times. My /etc/hosts has a valid entry for my domain. Strangely, I am able to clone via https, which tells me the setup is basically working, except for the fact that gitlab-shell has an issue which I don't understand where it's coming from.

Also, the website works completely fine, even adding keys and users (which uses the gitlab shell). I don't understand why it gives the checking script 401 Unauthorized and the website is working all right...

I'm not sure if this is a bug or a stupid mistake by me, in any case I'm sure this will help other people having the same issue.