The problem is not in the second example, but in the first, and in the algorithm not being right. You fell victim to the simplicity of your test example, since 3 elements is not enough for testing permutations. Here is a more representative example:

list1 = DeleteDuplicates@RandomInteger[15, 10]

(*  {1, 3, 8, 7, 14, 11, 13} *)

list2 = RandomSample[list1]

{8, 3, 11, 13, 1, 14, 7}

Creating the rules:

list1rules = Thread[list1 -> Range[Length[list1]]]
listdispatch = Dispatch[list1rules]

Now the key point: you need not just to apply the rules, which simply give you the positions of elements of list2 in list1, but you need the Ordering of those positions:

list2[[Ordering[list2 /. listdispatch]]]

(*  {1, 3, 8, 7, 14, 11, 13} *)

Since at some point, some real sorting should take place.

The problem is not in the second example, but in the first, and in the algorithm not being right. You fell victim to the simplicity of your test example, since 3 elements is not enough for testing permutations. Here is a more representative example:

list1 = DeleteDuplicates@RandomInteger[15, 10]

(*  {1, 3, 8, 7, 14, 11, 13} *)

list2 = RandomSample[list1]

{8, 3, 11, 13, 1, 14, 7}

Creating the rules:

list1rules = Thread[list1 -> Range[Length[list1]]]
listdispatch = Dispatch[list1rules]

Now the key point: you need not just to apply the rules, which simply give you the positions of elements of list2 in list1, but you need the Ordering of those positions:

list2[[Ordering[list2 /. listdispatch]]]

(*  {1, 3, 8, 7, 14, 11, 13} *)

since at some point, some real sorting should take place. Have a look also here and here, where I gave detailed discussions of very similar ideas. I also once wrote a package called UnsortedOperations, which has a collection of functions for doing similar kind of manipulations. The package lives here, and comes with a notebook containing examples of use for all functions in it.