Best would be to use the line from the installation documentation (Download and install GitLab | GitLab), this is what I did on mine:
curl https://packages.gitlab.com/install/repositories/gitlab/gitlab-ce/script.deb.sh | sudo bash
this then worked fine. Change ce to ee in the above command depending on the version of Gitlab you are using.