Ahhh... you just caused a major flashback in my memory. I remember reading about Banach-Tarski paradox about 7 years ago or so and it gave me so many headaches. I think I read the paper explaining it trice and it still made no sense to me and on my second reading I was convinced there was an error in an equation somewhere.. I asked a math prof who's a brilliant theoretician and he explained it to me and it still made little sense. Then I read von Neumann's explanation and it finally started making some sense. The key to understanding it is, like with many other concepts, to ignore your intuition and trust the math behind it.
I'd say trust your intuition more than the math, but I'm more physicist than mathematician.
To prove Banach-Tarski, you need to assume Zermelo-Frankel set theory (just ordinary set theory) plus the uncountable axiom of choice.
In my view, this means the uncountable axiom of choice is false. This actually breaks far less than you would expect. For most practical purposes, you only need the countable axiom of choice, which is the intuitively reasonable version.
The main thing the loss of the uncountable version breaks is the Hahn-Banach theorem on spaces of dimension higher than countable infinity. This in turn breaks quantum field theory on free space (not in a box), but that's broken anyway.
I personally thought that the Banach-Tarski theorem was a mess, and these non-measurable sets had to go. So I started studying nonstandard-analysis: analysis with infinities and infinitesimals as genuine, arithmetically viable, quantities.
Imagine my distress: the same problem occurs, Banach-Tarski still holds, unless you go into the rather more weird, Smooth Infinitesimal Analysis or Synthetic Differential Geometry; basically, treating geometry as made up of little discrete infinitesimally small points.
