This is probably because the original merge had a conflict as well. (I can't prove that this is the case without having access to the repository and its commits.)
What you're seeing is a side effect of the fact that sometimes, git rebase can avoid some or all copies, and when it can and does avoid all copies, it ends up not doing anything at all. Doing nothing means no merge commits, but "copying" a merge that had a merge conflict before means that you see the same merge conflict again.
You can work around this problem with git rerere (and the rerere-train script, perhaps: see Smarter rebase avoiding redundant work?).
Long
Remember that git rebase works by copying commits. A simple interactive rebase starts by listing all the commits to copy, using pick commands for each such commit. This simple kind of rebase discards merges, though. Adding --rebase-merges (or -r) tells it: keep the merges, along with the original arrangement of commits. But there's a flaw in this whole concept: while it's possible to copy a non-merge commit, it's not possible to copy a merge commit.
What git rebase -r (and its older, poorer git rebase -p cousin) do instead, because they can't copy merges, is to re-perform merges when necessary. That is, after copying some number of old commits to new ones, with new and different hash IDs, they get to the point where it is time to "copy" a merge, and instead, they just run git merge directly.
For instance, given:
C--D
/ \
A--B G--H <-- source (HEAD)
/ \ /
/ E--F
/
...--o--o--*--o--o <-- target
and the command-line request git rebase -r target will generate a series of pick, label, reset, and merge commands to copy A, B, C, D, E, and F; then merge the copies ofDandF; then copyGandH`, so as to get:
C--D
/ \
A--B G--H <-- [abandoned]
/ \ /
/ E--F
/
...--o--o--*--o--o <-- target
\
\ C'-D'
\ / \
A'-B' G'-H' <-- source (HEAD)
\ /
E'-F'
where commit A' is a copy of A, B' is a copy of B, and so on.
But, with or without the -r option, consider a rebase operation that starts with:
...--I--J <-- target
\
K--L <-- source (HEAD)
You now ask Git, via git rebase, to copy commit K to a new-and-improved K that is exactly like K except that it comes after J, rather than coming after J. Then you tell Git to copy L so that instead of coming after K, it comes after the new copy of K.
Git realizes that the existing copy of K that comes after J already comes right after J. So the "copy" it needs to make is already there: git rebase just re-uses K directly. Now it must copy L to come after K, but look: L already comes right after K, so Git just re-uses L directly. The result is that nothing changes. (If, for some reason—and there are some reasons—you really want Git to copy K anyway, you can use --force-rebase or --no-ff or -f, all of which do the same thing.)
If you run this same rebase, being sure to use interactive mode, and use reword on K, now Git really does have to copy K to a new K' that is like K but has a different commit message. As a result, Git now really does have to copy L so that it comes after the new K' with the new message. The result is:
K'-L' <-- source (HEAD)
/
...--I--J <-- target
\
K--L [abandoned]
For a simple linear case like this one, the rebase always goes smoothly, but when you add -r to the mix, to force Git to "copy" (i.e., re-perform) a merge, if the original merge had conflicts, so will the new merge.
