"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! :)
Well, I decided to include some additional information.
Definition 1. Let $\mathcal{C}$ and $D$ be categories, $T\colon\mathcal{C}\to\mathcal{D}$ and $S\colon\mathcal{D}\to\mathcal{C}$ be functors. Then the pair $(T,S)$ is called an equivalence iff $S\circ T\cong I_{\mathcal{C}}$ and $T\circ S\cong I_{\mathcal{D}}$. In this case functors $T$ and $S$ are also called equivalences, and categories $\mathcal{C}$ and $\mathcal{D}$ are called equivalent.
It is a basic definition and Tim's answer shows why we need to use equivalence even more frequently than isomorphism. Here's another important definition:
Definition 2. Let $\mathcal{C}$ be a category, $\mathcal{S}$ be a subcategory of $\mathcal{C}$. Then the category $\mathcal{S}$ is called a skeleton of $\mathcal{C}$ iff it is a full subcategory of $\mathcal{C}$ and every object of $\mathcal{C}$ is isomorphic to precisely one object of $\mathcal{S}$.
Note, that if the axiom of choice holds, then every category has a skeleton. See also nLab article. The connection between equivalences of categories and their skeletons is described in the following proposition:
Proposition 1. Let $\mathcal{C}$ and $\mathcal{D}$ be categories, $\mathcal{S}_{\mathcal{C}}$ and $\mathcal{S}_{\mathcal{D}}$ be their skeletons. Then $\mathcal{C}\simeq \mathcal{D}$ iff $\mathcal{S}_{\mathcal{C}}\cong\mathcal{S}_{\mathcal{D}}$.
The proof follows from the fact that every category is equivalent to its skeleton and if two skeletal categories are equivalent, then they are isomorphic. You can also search Mac Lane's "Categories for the working mathematician" for the details.
Thus we can use the notion of skeleton instead of the original definition of equivalence, but sometimes it is not a simplification. As it was mentioned, even an attempt to prove that a category has a skeleton may lead to the set-theoretical difficulties. Tim also gave arguments.
You write: But why go through this whole process of defining this notion of equivalent categories if we can just create a single equivalence classes of objects via the equivalence relation of being isomorphic, and make morphisms defined on the same equivalence class "the same?"
Okay, it could be a good idea if we want to define something like a skeleton. But it isn't, because the straightforward applying this idea leads to wrong definition. Let's try to do this.
Definition 3. Let $\mathcal{C}$ be a category. Then define the graph $\text{Equiv}(\mathcal{C})$ in the following way: $\text{Obj}(\text{Equiv}(C))=\text{Obj}(\mathcal{C})/\cong_{\mathcal{C}}$ and $$\text{hom}_{\text{Equiv}(\mathcal{C})}([a],[b])=(\coprod_{a'\in[a],b'\in[b]}\text{hom}_{\mathcal{C}}(a',b'))/[(f\sim g)\Leftrightarrow(\exists a,b\in \text{Iso}(\mathcal{C})|\quad g\circ a=b\circ f) ].$$
But the graph $\text{Equiv}(\mathcal{C})$ doesn't inherit the composition law from $\mathcal{C}$. The graph $\text{Equiv}(\mathcal{C})$ doesn't even coincide with graph of any skeleton of $\mathcal{C}$ in general case. For example, it may paste two morphisms with the same domain: in the category $\mathbf{Finord}$ we have $\text{end}_{\text{Equiv}(\mathbf{Finord})}([2])=\text{hom}_{\text{Equiv}(\mathbf{Finord})}([2],[2])\cong2$, but $\text{end}_{\mathbf{Finord}}(2)=2^2=4$.
Best Answer
"$F(A)\cong G(A)$ naturally in $A$" means exactly the same thing as "$F$ and $G$ are naturally isomorphic".
The annotation "natural in $(-)$" starts pulling its weight for multivariable functors of mixed variance. Then, once we have a notion of "contravariant naturality", we can write succinct statements like
or