I am getting the error
Total 4 (delta 2), reused 0 (delta 0) error: RPC failed; result=22, HTTP code = 401
When pushing to a git repository on GitLab.
It used to work.
I had the same issue: public repos don't force git to authenticate on the first request, and git doesn't offer authentication (at least as of version 1.7.9) on subsequent requests of the same push.
This pull request for GitLab should fix it; tested on GitLab 6.3 but it may apply fine on older versions too (please let me know if it fails along with the version string).
On my CentOS 6.5, git 1.7.1 I encountered the same problem, I update git to 1.7.6.1 solved this.
See How to install git using git: