Well, it's good that it conflicts with your intuition, because the axiom of choice is intuitively correct.
But anyway, a good example is this: Let one of your sets be R, the set of all real numbers, and the other one be the Hartogs number of R.  Then by definition there's no injection from the second to the first, and if there were an injection from the first to the second, that would imply that the reals could be wellordered.
Actually this generalizes, and shows that trichotomy implies the axiom of choice.