The problem is that you also do a "meta" induction when proving choice for a finite number of sets and this "meta" induction fails in the transfinite or countable case.
To be more clear, the proof of choice for a number of sets sets usually goes something like this (I'm assuming choice is "the product of nonempty sets is nonempty").
Base case is vacuously true (you're given one nonempty set and want to prove it's nonempty).
Next, assume inductively that for any nonempty sets $X_1,...,X_n$, the product $X_1\times...\times X_n$ is nonempty. Now, given $n+1$ sets, $X_1,...,X_{n+1}$, you want to show their product is nonempty. By the induction hypothesis, there is an element $y\in X_1\times....\times X_n$. Also, there is an element $x_{n+1}\in X_{n+1}$ by assumption. Then $\{\{y,x_{n+1}\}, x_{n+1}\} = (y, x_{n+1})$ is an element of the product.
On the meta level, what you're saying by unraveling the induction is "I have $n+1$ sets $X_1,...,X_{n+1}$, and I know there is an element (which is itself a set because we're doing set theory!) in each $X_i$ which I'll call $x_i$. By using the axiom of pairing once, I can form the set $\{x_1,x_2\}$. By using it again, I can form the set $\{\{x_1,x_2\}, x_1\}$, which is the definition of $(x_1,x_2)$. Using the axiom of pairing two more times, I can form $(x_1, x_2, x_3)$. In general (i.e., by induction), by using the axiom of pairing $2(n+1)$ times, I can form the set $(x_1,x_2,...,x_{n+1})$. This set (element) is a member of $X_1\times...\times X_{n+1}$, and hence this product is nonempty!"
What goes wrong as soon as you try to adapt this to the countable or larger setting is on the meta level. Essentially, you'd have to apply the pairing axiom countably (or more) times to create the set $(x_1,...)$ which "should" be in $X_1\times...\times $. But naive set theory has taught us that just because we think something "should" be a set, doesn't mean it should (see, for example, Russel's Paradox). Thus, we at least cannot trust this proof to work in countable or larger settings. Of course, the failure of this approach doesn't mean there is NO way of proving choice from $ZF$, but it's known from other methods that you cannot prove choice from $ZF$ alone.
"Naturality" in a categorical sense is much more than "not depending on choices", and, also, is essentially unrelated to issues about the Axiom of Choice.
In the example of vector spaces over a field, we can look at the category of _finite_dimensional_ vector spaces, to avoid worrying about using AxCh to find elements of the dual. The non naturality of any isomorphisms of finite-dimensional vectorspaces with their duals resides in the fact that, provably, as a not-hard exercise, there is no collection of isomorphisms $\phi_V:V\rightarrow V^*$ of isomorphisms of f.d. v.s.'s $V$ to their duals, compatible with all v.s. homs $f:V\rightarrow W$.
In contrast, the isomorphism $\phi_V:V\rightarrow V^{**}$ to the second dual, by $\phi_V(v)(\lambda)=\lambda(v)$ is compatible with all homs, as an easy exericise! This latter compatibility is the serious meaning of "naturality".
True, if capricious or random choices play a role, the chance that the outcome is natural in this sense is certainly diminished! But that aspect is not the defining property!
Edit (16 Apr '12): as alancalvitti notes, the ubiquity of adjunctions, and the naturality and sense of "naturality", and counter-examples to naive portrayals, deserve wider treatment at introductory levels. After all, this can be done with almost no serious "formal" category-theoretic overhead, and pays wonderful returns, at the very least organizing one's thinking. Distinguishing "characterization" from "construction-to-prove-existence" is related. E.g., "Why is the product topology so coarse?": to say that "it's the definition" is unhelpful; to take the categorical definition of "product" and _find_out_ what topology on the cartesian product of sets is the categorical product topology is a do-able, interesting exercise! :)
Best Answer
The axiom of choice is an axiom of set theory, and it is used when implicitly assuming that the universe consists of sets, and sets alone. That is - everything is a set.
For example, $0=\emptyset$ and $1=\{\emptyset\}$. Since everything is a set, consider a set $X$ and all its elements are non-empty sets themselves. Formally $\forall y(y\in X\rightarrow \exists z(z\in y))$.
The axiom of choice asserts the existence of a function whose domain is $X$ and its range is $\{z\mid\exists y(y\in X\land z\in y)\}$ (often denoted $\bigcup X$). The function has a very special property, namely $f(y)\in y$. It chooses someone from every element of $X$.
Some examples (which do not require the axiom of choice) are, $X=\mathcal P(\mathbb N)\setminus\{\emptyset\}$ that is all the non-empty subsets of natural numbers.
We can have $f(A)=\min A$, that is the least element of $A$ is returned. We can require something slightly more peculiar $f(A) = \min\{a\in A\mid a\text{ is even}\}$ if such $a$ exists, or $\min A$ otherwise.
These are two examples which do not require the axiom of choice since we are able to specify in a uniform formula who do we want to pick from every $A$.
A useful equivalence of the axiom of choice is Zorn's lemma. This lemma is somewhat complicated, but it asserts that if $(A,<)$ is a partially ordered set, and every linearly ordered subset of $A$ has an upper bound, then there exists a maximal element.
To elaborate on that, if $A$ is a non-empty set, and $<$ defines a partial order on $A$, if every $C\subseteq A$ which has the property $\forall a\forall b(a<b\lor b<a\lor a=b)$ has some $x\in A$ such that $\forall a(a\in C\rightarrow a<x)$ then there exists a maximal element - some $x\in A$ for which the property $\forall a(a\neq x\rightarrow a<x)$ is true.
Zorn's lemma is very useful in algebra, and used in the proof that every field has an algebraic closure; every vector space has a basis; and every ideal can be extended to a maximal ideal (and many many many other uses).
The proof uses heavily the axiom of choice (not surprisingly, since the two are equivalent) and in a nutshell we take one element, then $\{a_0\}$ is linearly ordered, therefore if $a_0$ is not maximal in $A$ we can extend it. That is the set $\{b\in A\mid a<b\land a\neq b\}$ is non-empty, and we can choose from it. We choose from non-empty subsets of $A$ until we either "find" a maximal element, or derive contradiction to one property or another.
I use "find" because many times the maximal element is one we cannot describe nicely by a sentence (and in fact without the axiom of choice there are vector spaces without basis, fields without algebraic closures and so on).
To understand the axiom of determinacy first we need to understand what there is to be determined.
Take $A\subseteq\mathbb N^\mathbb N$, that is a set of infinite sequences of natural numbers.
Now we play a game, I will be Player I (P-I) and you will be Player I (P-II). I will choose some $n\in\mathbb N$, and then you will choose another. The game is infinitely long and will have another round for every finite number of rounds.
Note that in the $n$-th round we have $x_n$ and $y_n$ (I chose $x$'s and you choose $y$'s). This defines a sequence: $$a_n =\begin{cases}x_k & n=2k\\ y_k & n=2k+1\end{cases}$$
We say that I win the game if $\langle a_0,a_1\ldots\rangle\in A$, otherwise you win the game. If there is a strategy assuring victory for either one of us then we say that the game is determined. This is to say there is a function from $\mathbb N$ to $\mathbb N$ that given the current state of the game will give me a possible tail segment which assures one of the player's victory. (Note that there are usually a lot of possible strategies).
For example $A$ will be all the sequences which are constants $a_n=k$ for some $k$. Clearly you have a winning strategy. Whatever I chose at first, choose something else and I have no chance of winning.
Another example is $A$ will be the set of sequences that $a_n$ is even whenever $n$ is even ($a_n=n$, for example). All I have to do is choose even numbers in my turn, and I cannot lose.
The Axiom of determinacy asserts: Every game is determined. That is, if we play this sort of game then regardless to which set of sequences we have chosen, one of us can win.
The conflict with the axiom of choice is a bit technical for this post (and the part about determinacy could surely be phrased better by someone else), the idea is as such. If we assume the axiom of determinacy, then every game is determined. We will define $A$ by a transfinite induction. Since at each step during the game the collection of winning strategies is non-empty. We simply choose such winning strategy and ensure that it will not work by adding a sequence to $A$, repeating the process "enough" times we ensured that no strategy exists to determine the winner after any finite number of turns. This contradicts the assumption that every game is determined.
Determinacy is somewhat of a technical axiom, and while it was very natural to postulate this axiom in some parts of set theory (namely descriptive set theory), the mainstream mathematics has been made very comfortable with the axiom of choice, and as Theo points out in the comments some pathologies which we are used to are gone when assuming the axiom of determinacy.
This makes the axiom of choice more common in modern mathematics than determinacy. Things can change, though... things can change.
Added:
To understand the need for the axiom of choice, we return to Bertrand Russell's wonderful analogy. Given infinitely many pairs of shoes, you can always choose one from each pair, but to choose a sock from infinitely many pairs of socks you need the axiom of choice.
What does that mean? Well, given shoes you can easily say "Pick all the left shoes", and regardless of how many pairs are given in each pair there is exactly one left shoe. This defines a function which chooses an element of each pair. On the other hand socks are indistinguishable and you cannot say which one is the left and which one is the right.
What does that mean indistinguishable? Well, given one pair of socks $\{a,b\}$ we can always say "Oh, this is $a$ and this is $b$", even if our assignment of $a$ was arbitrary. Every time we are given three pairs of socks we can ad-hoc assign each pair as $a_i, b_i$ and pick the ones we assigned as $a_i$. However if there are infinitely many pairs of socks, can we always make such assignment? Well, only if we assume the axiom of choice holds.
The point is that a pair of socks has two elements in it. These are always distinct and we can always examine the pair by itself and distinguish between the two socks. We can always distinguish between three, four and five socks at once; as well ten or fifteen pairs of socks. We simply assign each collection of socks with different names to be able and temporarily tell which sock is which, then we can choose the names we would like.
Mathematically speaking if we are given a finite collection of non-empty sets, if we do not actually care about the choice of elements, as long as we choose exactly one from each set, it is always doable. First we need to understand that "not caring" means that we only require $f(A)\in A$ which is of course doable since $A$ is non-empty. However, in mathematics it is not enough to claim things, one has to prove them as well. In this case, we can simply write the following statment (assuming $A_1,\ldots, A_n$ are our non-empty sets):
$$\exists x_1\ldots\exists x_n(x_1\in A_1\land x_2\in A_2\land\ldots\land x_n\in A_n\bigwedge f(A_1)=x_1\land f(A_2)=x_2\land\ldots\land f(A_n)=x_n)$$
That is to describe exactly (I am somewhat cheating here, I did not describe it exactly, but I gave a close enough approximation) how $f$ looks like, it is the function (however a function may be defined set theoretically) that after fixing $x_i\in A_i$ simply returns $x_i$ as the choice from $A_i$. Since this is a finite collection of pairs we can describe this sort of choice.
If we have one pair then this sentence is very short, as we keep on adding pairs we will write longer and longer sentences. If we finally have infinitely many pairs then we cannot write this sort of sentence. We need to find a different formulation. This is where the ability to uniformly distinguish some unique element in each $A_i$ comes to help. Suppose $\varphi(x)$ is the property of being a left shoe. Let $B=\{B_n\mid n\in\mathbb N\}$ be a collection of infinitely many pairs of shoes. If we want to choose from each pair, we can simply do it as such:
$$\forall X(X\in B\rightarrow \varphi(f(X)))$$
Since there exists exactly one element, $a$ in every $X$ for which $\varphi(a)$ is true (i.e. there is exactly one left shoe in each pair of shoes) this implies the function $f$ is nicely defined, in a finite (and even short) sentence.
Now we return to the socks. There is no property $\varphi(x)$ such that in every pair of socks there is exactly one sock for which $\varphi$ is true. This means that we cannot write a very nice sentence as above, to choose one sock from each pair!
This is the (with a capital "the") key of the issue here. In a finite collection you can always distinguish every element from every other element. When looking at an infinite collection you may not be able to have this luxury.
What does that mean mathematically? It means that you may not be able to write a finite sentence to help you choose from infinitely many pairs without the axiom of choice - which asserts this sort of choice exists (it may not be computable or even definable except for knowing it exists somewhere in your universe, and therefore you can take an arbitrary one and use it for a while).