They're not quite identical. They may make the same logical change, but they are based on different history.
The mistake you made is to rebase commits that have been published on another branch. Generally you would throw away the "originals" after rebasing, but in this case, the master branch already knows about them (due to the merge), so that may not be an option.
How you proceed with fixing it depends on what your history looks like, and how much of it you are willing to rewrite. From your description, your history looks something like:
F----G <-- original branch
/ \
...A--B--C--D--E--M <-- master
\
F'--G' <-- rebased branchwhere F' is the commit matching F, and so forth. Due to merge M, master contains the commits from the original branch, but your newly rebased branch has the matching ones.
If you have not actually published the merged value of master to anyone else, and you have not built anything on top of master, then it is safe to redo that merge, like:
git checkout master
git reset --hard HEAD^
git merge your-branch
If you have built on top of master, you can still redo the merge, but you would then need to replay those new commits on top of the new merge:
# make a new branch at master just before the merge; you will have to
# find the commit id of the merge via "git log" or gitk
git checkout tmp-branch M^
# now redo the merge, using the rebased commits
git merge your-branch
# and now we rebase master, using just the commits from _after_ the
# merge, on top of our re-done merge
git rebase --onto tmp-branch M master
# the rebase command leaves us on "master" as a side effect; we can now
# delete tmp-branch
git branch -d tmp-branch
If you have published your merged master for others to build on top of, then you probably don't want to rewrite it, as it will cause pain for others. Just live with the commits you've published, and redo your changes as new commits on top. To restore the state of your-branch to what it was before the rebase, look in the reflog ("git log -g your-branch"), then reset it ("git checkout your-branch; git reset --hard your-branch@{1}" (or whatever reflog entry looks to be correct)).
You may want to also look at this thread, which shows a similar problem, and in which I drew a lot more pictures, which may help explain:
http://article.gmane.org/gmane.comp.version-control.git/161823
-Peff