When you rebase a branch, you have to rewrite the commits for any commit which is above the commits in the branch onto which you are rebasing. This is because one of the properties of a commit is its parent (or parents). When you rebase, you’re changing the parent of the oldest local commit on your branch – and thus changing the commit hashes of all of your local commits, since this change bubbles up through the commits transitively.
Since you’d already pushed the branch, you should have merged in the source branch, rather than rebasing against it. It is possible to “force push” your new branch (using the -f flag), but a normal push won’t work, because the integrity of the branches history will be disturbed. If you are collaborating with others on this branch, force pushing is a bad idea, as it will cause other collaborators to become very confused when their history suddenly doesn’t match.
TL;DR – If you’re not collaborating, push the branch using push -f. If you are, reset the branch to the previous state, and merge in the source branch, instead.