What's behind the Banach-Tarski paradox? The discovery of the Banach-Tarski paradox was of course a great thing in mathematics but raises the issue of the relation between mathematics and reality. Empirically there are good reasons for faith in mathematical proofs: well derived mathematical theories and formulas, used in an accurate manner in science, really bring observable results. I don't know any scientific failures where mathematical results was blamed.
Naturally constructive proofs are preferable but there shouldn't be any problem with non-constructive proofs: the mathematical-logical machinery should guaranty the expected success. With or without the use of the law of the excluded middle!
So how to explain the non-intuitive theorem of Banach-Tarski? Which are the "weak pillars" or combinations of them? Personally I can't see the axiom of choice as a problem, since it only is a condition of what's to be called a set. Is the theorem perhaps a sign of lack of continuity in reality?

I really would like a big list of suggestions what "axioms" could be
  changed to avoid the "possibility" of the the theorem.


I have been re-considering. Suppose that a new discrete theory about space and time was developed and was found to be consistent with observations. How long would it take before a corresponding theory was developed from a pure geometrical perspective? Compare with the corresponding theories of Heisenberg and Schrödinger!
What was explained in one way in the discrete theory maybe was described in a totally differnt way in the continuous theory? And who knows, maybe similar constructions as in the paradoxes of Banach-Tarski and Sierpinski-Mazurkiewicz, would be used to explain the expansion of what is now called dark energy? And even "worse", to explain the result of high energy proton- proton collisions?
It strikes me that the relative terms of consistency as is used in mathematics is all what is needed for the mathematical material to be used in scientific theories. Physicists do sometimes use mathematics in extraordinary ways and get good results.
But that does not make it less interesting to ponder the pillars of the "paradoxes".
Also, thanks for reopen and for great answers!
 A: I would suggest that the axiom at fault is the axiom of infinity. The physical world deals only with finite sets, which is why we never encounter these paradoxical decompositions in practice; they come up automatically any time infinite sets are involved.
Almost by definition, an infinite set is one which is equal in size to a proper subset. Geometrically speaking, you can translate the set of natural numbers by one unit and obtain the exact same set, but leaving out one point. As mathematicians we often take this for granted, but this should already get your common-sense-warning-bells ringing - you can just pick something up, move it, and have it fit inside itself with room to spare!
Ok, but that's a set that "runs off to infinity," so as long as we restrict to bounded sets we're fine, right? Nope, you can wrap a copy of the natural numbers around a circle (rotating by an irrational multiple of pi each time), and simply by rotating this set, you again get a copy of this set but with points removed. No axiom of choice involved.
Ok, but all these examples aren't as bad as Banach-Tarski, you may say - yes, you get a set which is congruent to a proper subset, but you can't split a set into two copies the same size as the original. 
Well lo and behold, the deep dark secret of paradoxical decompositions: A set in the plane which is congruent (note: not just equidecomposable, actually congruent) to two disjoint copies of itself. And it's a set that you can explicitly define. No axiom of choice necessary. The Sierpinski-Mazurkiewicz paradox.
The only difference between this paradoxical decomposition and the Banach-Tarski paradox is that this one doesn't break our intuition of measure (the sets involved are measure zero). But the proof of Banach-Tarski actually starts off almost identically to this one; the paradox comes from an algebraic construction (essentially, the meat of the Banach-Tarski paradox is that the free group on two generators embeds into the group of rotations of a sphere). The only problem is that this construction gives a measure zero subset of the sphere. The axiom of choice simply allows you to "flesh out" the paradoxical pieces you found to cover the whole ball. Its role is that of a bridge from zero measure to positive measure (which is why it's so useful in analysis and we should most definitely not get rid of it); the paradox itself comes from algebra. And all this algebraic construction needs is for infinite sets to exist.
Though it feels really campy to end with a Wikipedia quote, I feel their article on paradoxical sets says it best: "Paradoxical sets exist as a consequence of the Axiom of Infinity. Admitting infinite classes as sets is sufficient to allow paradoxical sets."
A: There is a splitting of the Banach-Tarski theorem into a constructive and a nonconstructive part.
The first, which as von Neumann showed is the principle behind many similar problems, is the existence of a noncommutative free group $F$ inside the group of congruences of 3-dimensional space.  The proof that such a group exists does not use the axiom of choice, and is the hard part of the proof that uses "real math facts". 
The second, nonconstructive part is to take a cross-section of the quotient by the action of a (2-generator subgroup of) $F$ so as to get the pieces of the decomposition.  This uses the axiom of choice, is probably equivalent to AC or a slightly weaker uncountable choice principle, and is a clever, but easier and more formal part of the argument.
What would survive without axiom of choice or the like are the proofs that the Euclidean isometry (or rotation, volume-preserving, etc symmetry) groups contain pairs of elements generating a free subgroup.  That would no longer imply a paradoxical decomposition into congruent pieces, but it is also possible that the nonconstructive theory can be adapted in some way to get analogous restriction on the existence of congruence-invariant measures from the existence of the free subgroup.  For example, if you allow closures of the pieces and not only congruent copies, then no AC is needed to get a decomposition:
http://www.ams.org/journals/jams/1994-07-01/S0894-0347-1994-1227475-8/S0894-0347-1994-1227475-8.pdf

We also prove related "paradoxes" which ... are entirely constructive and make no use of the Axiom of Choice.  ... one can find a finite collection of disjoint open subsets of the unit ball which can be rearranged by suitable isometries to form a set whose closure is a solid ball of radius 10^10  [Dougherty and Foreman, Banach-Tarski Decompositions Using Sets with the Property of Baire]

A: EDIT: Maybe more precisely, not the assumption of the existence of uncountable sets, but allowing the existence of uncountable sets is one of the issues. In our universe/reality there are finitely-many atoms ( someone around here may have a good estimate of the total amount), which do not allow for the constructions in Banach-Tarski.
A: If anything, the non-reality of the Banach-Tarski decomposition is because the sets the theorem speaks about lack continuity that reality does have. Even though the theorem divides the sphere into a finite number of "pieces", those pieces cannot exist as physical objects; the points inside and outside of the set are too finely intermingled to make it reasonable to cut it out physically from a continuum.
However, we don't need to go to Banach-Tarski, or even to the Axiom of Choice or non-constructiveness in order to see this situation.
For example, consider a cube in $\mathbb R^3$ and divide it into two pieces: one that consists of points with at least one rational coordinate, and another one consisting of those points that have all coordinates irrational.
These "pieces" are just as unphysical as the pieces in the Banach-Tarski decomposition, but defining what they are requires no mathematically questionable foundational assumptions at all. They don't seem "as paradoxical" as the Banach-Tarski pieces, because they happen to be Lebesgue measurable -- but that just tell us that simply being measurable doesn't mean that a set of points is physically meaningful.
A: There is an implicit axiom that people assume

sets of points in the plane should be meaningful geometrically

This, of course, isn't an axiom of ZFC or of real analysis; this is an implicit expectation of people who want to apply set theory to geometric problems.
Measure theory, one of the more general and powerful tools for defining contexts where we can "measure" things, gives us the phrase "measurable set", and the tools of measure theory only really apply to measurable sets.
Of course, most things you do are measurable. People want to go so far as to think of the adjective "measurable" as being a mere technicality that one doesn't really have to pay attention to.
Of course, problems with this axiom were already known prior to the discovery of the Banach-Tarski paradox. However, they were weird and complicated, so people don't feel so strongly about this axiom failing.
There's sort of a metaprinciple that if you start with something reasonable, end with something reasonable, and do reasonable things inbetween, the result should be meaningful. The axiom people really want to assume is

reasonable sets of points in the plane treated reasonably in a way that produces reasonable results should tell us something meaningful

And to be fair, this isn't a terrible thing to want to assume; it means we can ignore a lot of technicalities if things don't smell wrong. And, in fact, a huge amount of calculus just works under these conditions; there are a lot of theorems that support the above axiom in a wide variety of situations.
The Banach-Tarski paradox, however, closes the rest of the loopholes. A ball is a reasonable set. Two balls are a reasonable set. Splitting a ball into finitely many pieces is reasonable. Moving sets around with Euclidean motions is reasonable.
The only weird thing is that the individual pieces are non-measurable.
The fact that we did everything reasonably except for that one technical condition and failed to get a reasonable result appears to irk people quite a lot. It drives home the point that if you want to use measures, you to actually need to know whether the things you're doing result in measurable sets.
Now, as for the specific question you asked, the only axioms we need to get rid of are the two blockquoted axioms I stated above. They were never axioms of mathematics anyways, so from that perspective we're already done!
Sure, it's technically still a theorem of mathematics, but we were interested in measuring things, and it's not a theorem about measurable sets, so since we're supposed to talk about measurable sets, the theorem isn't relevant to us and there's nothing to be worried about.
(naturally, there are people who are more vested in their implicit axioms rather than the convenience that the axiom of choice gives us, thus rejecting the axiom of choice in favor of adopting the axiom that all subsets of the real numbers are measurable)

And a bonus joke: what's an anagram of Banach-Tarski?

 Banach-Tarski Banach-Tarski

