I was getting the above mentioned error message when I tried to push my current branch foobar:

git checkout foobar
git push origin foo

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)

So, what worked for me is to push my current branch by using:

git push origin foobar:foo

... and to cleanup with git branch -d

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