The second part of your post has been pretty much answered. I just want to nitpick this bit. There are still debates going on over this, but here’s a rough idea of the functionally predominant view:
A collection of axioms describe a certain kind of structure. Sometimes the structure is uniquely defined (“up to isomorphism”) like the natural numbers, and sometimes it’s more general like the notion of a group. This much is pretty uncontroversial.
For a long time now, sets have been used as the building blocks of everything else, but they’ve got some big problems. For one, to use a set-theoretical background you have to choose whether or not to use various axioms, and the oddest one is the Axiom of Choice, and its equivalents Zorn’s Lemma and the Well-Ordering Principle. The problem arises that when you’re doing algebra it’s really nice to have Zorn’s Lemma around. In fact, it’s almost indispensible. However, when you’re doing analysis (think “calculus, but more so”) or point-set topology, the Axiom of Choice gives you weird things like non-measurable sets (as MikeS mentioned) and outright absurdities like Banach-Tarski. Even worse, algebraic topology gets a mixed bag. The upshot is that the Axiom of Choice is so nice for algebra that mathematicians generally accept the weirdness, but there are a few holdouts.
Anyhow, what if we never had to make that choice? Enter topoi. A topos is a kind of mathematical structure which does all sorts of nifty things. In particular, various topoi are really good at providing models for various kinds of set theory. Originally, of course, topoi arose from a field rooted in sets (usually thought of with Choice), and there’s a topos of sets, which is sort of like emulating a computer in its own software. You can also construct topoi of other variations on the notion of sets. These can, for instance, provide models of set theories which reject Choice.
So there’s a push on (among people who even think about such things anymore) to try to replant the whole tree of mathematics in topoi from the beginning. Now the question can be answered, “The Banach-Tarski paradox involves cutting infinitely finely, would take forever to make the choices the Axiom of Choice tells us can be made, and only holds in Choice topoi to begin with”. Of course, there’s no evidence on either side that Choice holds in whatever topos the real world occupies or not, but the Intuitionists (people who hold Banach-Tarski up as an absurdity, among other things) would suggest that the real world’s logic doesn’t contain Choice.
 Oddly enough, most modern mathematicians don’t pay much attention to mathematical philosophy. This is the view that (as far as I can tell) best describes “how mathematicians really do math”.
 The Axiom of Choice says that if you have any collection of sets indexed by another set, you can choose one element of each set. It’s nontrivial when the indexing set is very infinite.
Well-Ordering says that the elements of any set can be put into a line so that any subset contains a least element. Just try this with the real numbers to see how things start to go weird.
Zorn’s Lemma is harder to describe. Basically if you’ve got a notion of “greater than”, but not every pair of elements are comparable (think about (x,y) > (z,w) if x>y and z>w. Then (1,2) and (2,1) are incomparable), and for any sequence of increasing elements (each “greater than” the last) you can find an element that’s greater than all of the elements of the sequence, then the set contains at least one element that no element is greater than (though other elements may be incomparable).
Although all three are logically equivalent, mathematicians (well, those who are like this mathematician) are fond of noting that “The Axiom of Choice is obviously true, the Well-Ordering Principle is plainly false, and who knows about Zorn’s Lemma?”