TL; DR
The --preserve-merges flag simply tells git-rebase to try to recreate merge commits instead of ignoring them. It does not give git rebase the ability to remember how merge conflicts were resolved, i.e. it does not record conflict resolutions for future use. What you want to use for that is rerere.
In your toy example, the conflict arising during the rebase is exactly the same as the one you resolved during the preceding merge. If you had activated rerere before the merge, you wouldn't have had to resolve that conflict again during the rebase.
If you anticipate that you will merge, then rebase a branch, you should activate rerere so that, in the future, you only need to resolve a given merge conflict once, not multiple times.
Detailed explanation
Let's break down your toy example.
git init
echo Hello > Hello.txt
git add Hello.txt
git commit -m "Create Hello.txt (commit A)"
git tag start
echo World! >> Hello.txt
git commit -am "Change to Hello World (commit B)"
git checkout start
git checkout -b branch
echo Dave >> Hello.txt
git commit -am "Change to Hello Dave (commit C)"
So far, so good. Right before your first git merge command, your repo looks like this:

In commit A, Hello.text contains
Hello
In commit B, Hello.text contains
Hello
World!
And in commit C, Hello.text contains
Hello
Dave
Now, when you try to merge master into branch by running
git merge master
Git reports a merge conflict because it has no way of figuring out, on its own, whether the contents of Hello.txt after the merge should be
Hello
World!
Dave
or
Hello
Dave
World!
or something else...
You resolve that conflict by overwriting the contents of Hello.txt with Hello World, Dave!, staging your changes, and completing the merge commit.
echo "Hello World, Dave!" > Hello.txt
git add Hello.txt
git commit -m "Merge branch master into branch (commit D)"
Your repo now looks like this:

Then you run
git checkout start
git checkout -b goodbye-branch
echo Goodbye > Goodbye.txt
git add Goodbye.txt
git commit -m "Add Goodbye.txt (commit E)"
At that stage, your repo looks as follows:

Now you run
git checkout branch
git rebase -p goodbye-branch
but experience a conflict. Before explaining why this conflict arises, let's look at what your repo would look like if that git-rebase operation were successful (i.e. conflict free):

Now let's see why you run into the same conflict in Hello.txt as during your first merge; Goodbye.txt is not problematic in any way, here. A rebase can actually be decomposed in a sequence of more elementary operations (checkouts and cherry-picks); more on this at http://think-like-a-git.net/sections/rebase-from-the-ground-up.html.
Long story short... In the middle of your git rebase operation, your repo will look as follows:

The situation is very similar to that right before your first merge:
in commit B', Hello.text contains
Hello
World!
And in commit C', Hello.text contains
Hello
Dave
Then Git attempts to create merge B' and C', but a merge conflict arises for the exact same reason as the first merge conflict you experienced: Git has no way of figuring out whether the Dave line should go before or after the World! line. Therefore, the rebase operation grinds to a halt, and Git asks you to resolve that merge conflict before it can complete the rebase.
What you can do about it: use rerere
Git's rerere is your friend, here.
The name stands for "reuse recorded resolution" and as the name implies, it allows you to ask Git to remember how you've resolved a hunk conflict so that the next time it sees the same conflict, Git can automatically resolve it for you.
[...] if you want to take a branch that you merged and fixed a bunch of conflicts and then decide to rebase it instead - you likely won't have to do all the same conflicts again.
If rerere had been enabled,
git config --global rerere.enabled true
before the merge, then Git would have recorded how you resolved the merge conflict when creating commit D, and would have applied the same resolution when it encountered the same conflict during the subsequent rebase. The conflict would still have interrupted the rebase operation, but it would have been resolved automatically. All you would have had to do is git rebase --continue.
However, it looks like rerere wasn't already activated before the merge, which means Git must have kept no record of how you resolved the conflict the first time. At this stage, you can either activate rerere now and resolve all those same conflicts manually again, or use the rerere-train.sh script (see also this blog post) to use the existing history to pre-seed the rerere cache.