For people who love a clean, linear history, this can be frustrating, because it creates a new commit that doesn't add anything new, it just merges two branches. At my current project, PRs get merged very slowly, and after every PR gets merged, we merge master back into all the branches, which has lead to a ridiculous number of merge commits, and the guy who loves clean history won't stop complaining about it.
The problem is: if you rebase instead, you don't actually change the old commit, you make a new commit that contains the same content change as the old one. But it's a new commit, different from the one you already pushed to remote. So now you want to push your new rebased commit (as well as everything from master) to remote, and git says that remote has a commit that you don't have locally. So it wants to rebase or merge that remote commit onto your local rebased commit, despite the fact that they contain the same change! Now if you choose to rebase your local changes onto the remote commit, it rebases all the commits that you just merged from master, creating new commits for them. Then pushes them to remote. Then you still can't merge your PR, because it now still doesn't have the original (unrebased) commits from master, because you just rebased them. But you've duplicated a ton of commits. This is a mess.
There are 3 ways around this:
* Replace the first rebase with a merge, merging master into your local branch.
* Replace the second rebase with a merge, from when you pulled remote when you wanted to push, duplicating the one commit you meant to rebase.
* throw away the old PR and create a new one.
The first and third are the good options. The second is bad because it has a duplicate commit, but it's not nearly as bad as when you tried to rebase twice in a row.
Seriously, if stuff gets complicated, throw away your PR. Or avoid it getting complicated by always merging. If you want clean history, your only option is to throw away your PR every time you merge master back into your branch. It's either that or accept extra merge commits.
A dirty shortcut to creating a new PR is to force push. This will throw away the original commit on remote and overwrite it with your new rebased commits. This will work fine as long as nobody has checked out that branch in the mean time. If someone else has checked it out and pushes to your remote branch again, they may still reintroduce the old unrebased commit, and you'll still have that duplicate commit.
I usually just accept extra merge commits. Sometimes I force push, but I really try not to. You have to be sure nobody else is using that branch. In a complicated setup with lots of developers, automated tests and build servers, I'm reluctant to count on that.