We show that for any countable homogeneous ordered graph G, the conjugacy problem for automorphisms of G is Borel complete. In fact we establish that each such G satisfies a strong extension property called ABAP, which implies that the isomorphism relation on substructures of G is Borel reducible to the conjugacy relation on automorphisms of G.