I have seen this occur when the SSL certificate file configured for the gitlab instance web server is only the certificate for the server and not not the complete certificate chain (root CA plus any intermediates). Adding the complete certificate chain to the .crt file configured for the web server (/etc/gitlab/ssl/your.domain.name.crt by default) may rectify this.
Your browser is happy to work it’s way back to a root of trust already existing in the trust store but command line tools seem to require that you provide the whole chain.
See more information at: https://medium.com/@superseb/get-your-certificate-chain-right-4b117a9c0fce