Hi Dan,
your problem is that you used RightArrow, whereas you should use Rule. This is a bit difficult to see in the output:

So it looks the same but it is not. The following lines show what is going on:
{a, b, c} /. {c \[RightArrow] b, b \[RightArrow] a} // Hold // FullForm
{a, b, c} /. {c -> b, b -> a} // Hold // FullForm
The sceenshot shows the output.

So the issue is that both RightArrow and Rule are rendered in the same way. If you type it in as -> it should work.
Cheers,
Marco