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][1] and [here][2], 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][3], and comes with a notebook containing examples of use for all functions in it. 


  [1]: http://www.mathprogramming-intro.org/book/node466.html
  [2]: http://www.mathprogramming-intro.org/book/node596.html
  [3]: http://www.mathprogramming-intro.org/additional_resources.html