This error came up every time I tried to do a push using SourceTree. I didn't try the command line client.
I figured this was a little odd since I am the master (owner) of this private repository and even though it was a protected branch according to my GitLab settings, I should have been able to push changes to it.
I logged into the GitLab website and checked whether I had any web hooks configured and I didn't, so that couldn't have been the problem.
I tried doing a push again and all of a sudden it worked! So I am guessing that logging into the GitLab website had reset my login session or something and let me do a push to my repository.