Qiaochu's answer is great, and reflects exactly what a mathematician should feel about the Banach-Tarski theorem.
I would like to add another opinion, as someone who works mostly in a choiceless context I can assure you that mathematics has many surprises in store for you once you give up the choice needed for Banach-Tarski.
You might end up with the bizarre universe in which there are no free ultrafilters on $\mathbb N$; the real numbers might be a countable union of countable sets; or it might be possible to cut the real numbers into more non-empty parts than elements.
There is always a "paradox", which is really just a counter-intuitive theorem, hiding in the dark corners of the universe. It tells you, in the philosophical level, just one thing:
Our intuition is completely developed by history and the axioms we are used to work with. Once you are completely used to the axiom of choice there is no surprise in the Banach-Tarski theorem, much like there is no surprise in Gödel's incompleteness theorems or in Cantor's theorem about the uncountability of the real numbers.
These are all theorems that shook the foundations of mathematics and caused people to shake their heads in disbelief, but eventually these theorems were accepted and nowadays people don't fuss about Banach-Tarski because it's one of the first thing presented in a course about measure theory: You can't measure everything in a translation-invariant way and with countable completeness.
The main issue is that in any strong enough theory there will be unexpected results, which is why the Banach-Tarski theorem - while very surprising - should not deter you from the axiom of choice, which makes infinitary things easier to deal with.