In my case git push
was trying to push more that just the current branch, therefore, I got this error since the other branches were not in sync.
To fix that you could use: git config --global push.default simple
That will make git to only push the current branch.
This will only work on more recent versions of git. i.e.: won't work on 1.7.9.5