NEVER AMEND OR REBASE A COMMIT YOU'VE ALREADY PUBLISHED!
If you publish a commit and somebody else fetches it, the commit is there to stay. When you amend or rebase, you create a new commit and forget the old one. But when somebody else already has the old commit, it will not get updated for them. So when they later merge, the two versions of the commit will merge causing havoc.
With this error, git is preventing you from pushing amended version of commits you've already published by mistake.
There are exceptions to the rule. If you are pushing to a backup that nobody works off, you can push new history there (it's called rewinding). And if there is a branch that is announced as being rewound (for example git's own "pu" branch and all topics not yet in "next"), it's obviously fine to rewind.
If you are certain you won't cause problems by this, you can tell git to go ahead and rewind by using
git push -f
It is also default for remotes configured as mirrors.
Note that some repositories can be configured with hook to prohibit rewinding or prohibit rewinding some branches anyway.