Earlier I claimed that even without the Axiom of Choice, the proof of the Banach-Tarski Paradox yields paradoxical results, so that the Axiom of Choice isn't the source of paradoxicality.
Here is something more precise. Without the Axiom of Choice, one can prove the following.
Almost-BT. Suppose B is a punctured ball, i.e., a solid ball without a center point, and v is a translation sufficiently large that vB does not intersect B. Then there are rigid motions (combinations of rotations and translations) α and β such that B can be partitioned into an infinite collection U of countable subsets with the property that each member A of the partition U can be further partitioned into four subsets A1, A2, A3 and A4, such that (a) A1 and αA2 are a partition of A and (b) vA3 and βA4 are a partition of vA. (This follows from the method of proof of Theorem 4.5 in the Wagon book on Banach-Tarski.)
In other words, one can partition B into a bunch of sets, each of which can then be divided into four pieces and reassembled into two copies of itself oriented the same way. Moreover, all the reassembly can be done using the same rigid motions. When we add the Axiom of Choice to the mix, we can basically take Bi to be the union of "the" sets Ai ("the" is in quotation marks because the sets Ai aren't unique given A; if they were, we wouldn't need Choice), and then B=B1∪B2∪B3∪B4=B1∪αB2 and vB=vB3∪βB4, and we have Banach-Tarski for punctured balls. (It's a bit of extra work to get Banach-Tarski for non-punctured balls, but that extra work doesn't need Choice.) But even without the Axiom of Choice, Almost-BT seems pretty counterintuitive.