After setting up my first repository on my GitLab instance, I received the following error message when pushing to my first repo:

remote: GitLab: The project you were looking for could not be found.

Turned out that I had a symlink in the path of to my data repository:

/var/opt/gitlab/git-data --> /data/gitlib

GitLab cannot deal with this and will then show this error message. The correct way to change the data directory is to change the config in /etc/gitlab/gitlab.rb to

git_data_dirs({ "default" => { "path" => "<YOUR_DATA_PATH>", 'gitaly_address' => 'unix:/var/opt/gitlab/gitaly/gitaly.socket' } })

Afterwards, you should be able to push / pull to your repositories.