+1  A: 

you have to pull first. Then push.

Luis Melgratti
Sometimes you also have to lift a bit to un-snag it.
BBetances
A: 

Force the push:

git push --force

You won't have to merge the differences, but you could lose some history on your local commits.

hughdbrown