We were receiving this error in gitlab and were stumped. Most of the articles online point to the branch being protected, but this branch was not in gitlabs protected branches section. In fact, no branch was in protected branches.
The fix for us was simple, we were actually pushing using a “deploy key” and the deploy key for this project was added by a team member who is no longer with the company. Meaning his user account in gitlab was disabled. We removed the deploy key and re-added it back in giving it write permissions and that resolved the issue.