Is there a *simple* example of how the axiom of choice can lead to a counterintuitive result? This question is quite subjective, but here goes:
The axiom of choice notoriously leads to many extremely counterintuitive results, like the Hausdorff, Von Neumann, and (most famously) Banach-Tarski paradoxes. Unfortunately, the proof of these paradoxes is also notoriously complicated, and it's not at all obvious why an axiom as seemingly innocuous (and, in fact, obvious) as the axiom of choice has such strange consequences.
Do there exist any examples of a simple chain of reasoning that leads from the axiom of choice to a counterintuitive result? (Though not necessarily a result as spectacularly counterintuitive as the Banach-Tarski paradox.) One which is simple enough that someone without training in advanced mathematics could understand the general train of logic (with perhaps a few steps fudged over)? I've never see an example that lets me intuitively understand why naive intuition "goes wrong" exactly at the step where we use the axiom of choice.
(To be clear: I'm not looking for a simple counterintuitive result that follows from the axiom of choice - Banach-Tarksi would qualify for that. I'm instead looking for a counterintuitive result that follows from the axiom of choice with a (relatively) simple proof.)
 A: Intuitive and counterintuitive results are tricky, as you said, it's a subjective thing.
Let me try and give you one example, a discontinuous solution to Cauchy's functional equation. Namely, a function $f\colon\Bbb{R\to R}$ satisfying $f(x+y)=f(x)+f(y)$.
It's not hard to see that such function is necessarily $\Bbb Q$-linear, so start with a Hamel basis for $\Bbb R$ over $\Bbb Q$, now pick any permutation of the basis, and extend it to a linear automorphism. Since you switched two basis elements, you didn't get a scalar multiplication, so you got a function which is not continuous or even measurable.
The last sentence also show that choice is necessary, since it is consistent with the failure of choice that all $\Bbb Q$-linear functions are measurable, which implies they are continuous, which implies they are scalar multiplications.

There are two issues here: the axiom of choice allows us to go "outside the structure", and infinite sets are weird.
Outside the structure?
One of the arguments about choice not being constructive is that the axiom of choice does not tell you how to obtain a choice function, it just tells you that such function exists. But because we are not limited to a specific construction, or constraints, or anything, this function does not have to obey any rules whatsoever.
From a more category-centered view, you can show that the axiom of choice does not hold for $\bf Ab$ or $\bf Grp$, because not every epimorphism splits in these categories (case in point, $\Bbb R\to\Bbb{R/Q}$).
But set theory doesn't care. Set theory ignores structure. There is a function, and its range is a set, and we have to deal with the fact that this might be counterintuitive and lead to things like the Banach–Tarski paradox or a Vitali set existing, because once you have a set (of representatives), the rest is just stuff you can do by hand.
So we get that the axiom of choice, by letting us split surjections, creates sets which sort counter our understanding of a given "structure". But of course, this is not the fault of the axiom of choice. This is our fault, for not understanding the interactions (or lack thereof) between "structure" and "sets" in general.
Infinite sets are weiiiiirrrrrdddd!
The second reason for many of the paradoxes is that infinite sets are weird. Look at the free group with two generators, $F_2$. Would you have expected it to have a subgroup which is generated by three generators? By infinitely many? No, that makes no sense. And yet, this is true. $F_2$ has a copy of $F_\infty$, and thus of $F_n$ for all $n$.
Or, for example, would you expect $\Bbb Q$ to be homeomorphic to $\Bbb Q^2$? That's also weird.
But these things don't even have to do with the axiom of choice. They have to do with the fact that we are finite, and these sets are not. And we base our naive intuition off finite sets, and then it fails. So we fix it, but we still base our intuition off of sets which "we hoped were good enough" (hence the ubiquity of the terms "regular" and "normal"), but these too fail us.
What's really funny is that when the axiom of choice fails, and you look at those extreme counterexamples (e.g. amorphous sets), then these look even weirder because choice is in fact very ingrained into our intuition.
To sum up?
The axiom of choice is really not at fault here. It lets us prove the existence of sets which lie outside of our intuition, because our intuition is honed to understand a given structure (e.g. topological structures, group structures, etc.), and it doesn't help when the infinitude of the sets lets us stretch and bend them in all kinds of ways to create weird stuff like the Banach–Tarski Banach–Tarski paradox.
Epilogue?
So there are two more minor points that I want to touch on.

*

*Our intuition is crap. We used to think that functions are "more or less continuous", then we learned that in fact almost none of them are continuous. Then we figured that almost all continuous functions are differentiable, but then learned that almost none of them are... and you see where this trend is going.
If you trace things back in history you run into physics or physical things in many cases. And physics is about phenomenon, things we can see and measures, which we automatically assume are continuous and "make sort of sense". But the mathematical world, as we have it in the post-post-modern era has a lot more to offer, and that sort of clashes with the roots, and sometimes with the intuition we carried from the original motivations.


*The axiom of choice is not really to blame. If you deny the Banach–Tarski paradox, and require that all sets of reals are Lebesgue measurable instead, then you can partition the real numbers into strictly more non-empty parts than elements. This is just bonkers. And it's not because of the axiom of choice, that is out the window here. It's because infinite sets are weird.
So what comes next? Next comes the fatalistic understanding that you can do nothing to change this. Unless you want to work in constructive mathematics, in which case you will run into a lot of other weird results, like non-empty sets that have no elements.
A: I'd say the easiest example would be the construction of Vitali sets.  I expect you already understand this, but here's how I might explain it to a 12th-grader.
Start with the naive concept of length, beginning with that of an interval, and the common notions that breaking up or shifting an interval doesn't change its length, that the lengths of a finite collection of disjoint intervals add, and that this extends to a countable sequence of disjoint intervals when its sum converges.  Stress here that the real numbers are not countable.  Point out that, since all of these lengths are nonnegative, the terms of such a sequence can be rearranged freely, and that therefore all this holds for any set of real numbers that can be built up from a countable collection of intervals.  From this quietly suggest, as intuition might dictate, that this can be extended to any set of reals.  All of this is intuitive enough.
Now, point out that two irrational numbers having a rational difference is an equivalence relation, and so produces equivalence classes.  Consider these equivalence classes restricted to $[0,1)$.  Apply the axiom of choice to get a set of one number from each such equivalence class.  Point out that shifting it by a rational number, cutting off the part outside the interval, and shifting it back to the other end will create a set that should have the same length.  Show that applying this for all the rational numbers in that interval will generate a partition.
So now you have a set of length one partitioned into a countably infinite collection of sets of the same length.  That length can't be zero, since the collection is countable, but it also can't be more than zero, since that would give their union infinite length.  Therefore, the axiom of choice allows you to construct sets of real numbers that do not have a length.
A: You may not have asked quite the question you want to ask. You sound like you're trying to understand exactly why some people object to AC - but that doesn't really have to do with the counterintuitive results. In particular, I'm not sure you're ever going to find a proof where "naive intuition 'goes wrong' exactly at the step where we use the axiom of choice", because I think in general, that isn't really where your intuition goes wrong, and it isn't the source of the counterintuitiveness of the result. It's literally just a coincidence that some counterintuitive results happen to involve choice in their proof.
It's a common (I think) misunderstanding that the objections to the axiom of choice have to do with it leading to strange results. Mathematicians have no problem accepting counterintuitive results. Counterintuitive results occur all the item with no axiom of choice. The trouble is that accepting the axiom of choice forces you to take a very questionable philosophical point of view on what it means to "exist".
Now, listen, to say that a mathematical object "exists" at all is already somewhat dubious. The number five doesn't "exist" like a table or an apple exists. We're already stretching the definition of the verb "to exist" just by doing arithmetic and geometry, but at least I can sort of imagine an object like a number or a circle. They exist in my mind, if nothing else, or I can describe them or even write down a formula for them.
But now we get to a set like the Vitali set. The construction of the Vitali set and the conclusion that its length is simultaneously zero and non-zero (or more precisely, that it has no reasonable concept of length) is definitely simple, although I don't know if the existence of non-measurable sets is exactly counterintuitive. The point is, though, think about how I show that this set "exists". All I do is, after partitioning the real number into a disjoint family of "dusts", I use choice to grab one point from each set.
I can't tell you one single number in the Vitali set. If you give me a number, I can't tell whether it's in the Vitali set or not. You want a picture? Forget it. A formula? Fat chance. I can't even imagine the Vitali set in my head. At this point I seem to have no excuse to be using the word "exists".
The reason this happened is because AC lets me claim something exists without having to explicitly describe it. This is really what people (used to) object to in AC.
