I was getting the above mentioned error message when I tried to push my current branch foobar
:
git checkout foobar
git push origin foo
It turns out I had two local branches tracking the same remote branch:
foo -> origin/foo (some old branch)
foobar -> origin/foo (my current working branch)
It worked for me to push my current branch by using:
git push origin foobar:foo
... and to cleanup with git branch -d