The issue as I understand relates to gitlab's use of the "Let's Encrypt" certificate authority. Apparently this is a relatively new authority and is unrecognized by the SSL software on the Ubuntu VM that Travis provides. I don't know of any workarounds at this time that can be applied in the VM that to overcome this problem. I also don't know if anything can be done on the gitlab side to mitigate it but suspect not. I do have a procedure that allows me to side-step the problem for my own case and can share that with anyone that needs it.