You did something wrong, but I'm having a hard time understanding what. One possibility is that you rebased something that you already pushed, and then tried to push it again. This is a big no-no, you should never rebase something that you've already pushed to a remote repo, or you'll run into various issues. Here's a short explanation of it
Let's assume this as the situation:
If your current branch is 'topic1', you can move commits A and B into topic2 branch by issuing
git rebase topic2 topic1(or just
git rebase topic2). Then the repo graph would look like
where commit D is what you considered as P'. Note, that the new parent commit needn't to be changed.
Or, more generally, if you need to move some commit(s) as descendant(s) of any commit (not necessarily the head of branch), you can use
git rebase --onto topic2~3 topic1~2 topic1 or
git rebase --onto Q P topic1 where Q and P are commits' SHA1s.
If these weren't what you intended, care to explain your situation a bit more?
If you want to completely remove it from you history, you could do the following:
git rebase -i <commit to remove>^
This will open your default editor (usually vi) with a list of commits, with the one you want to remove first. Remove it from the list, save, and quit. This should no rebase your branch without the commit you want to remove.
A "safer" approach is to leave the history in tact, so you can show that this feature used to exist, and was purposely removed. Just use
git revert <commit to remove>. This will create an additional patch that undoes the commit you want to get rid of. The main advantage is that you can edit the commit message, and explain why this feature is being removed.