How should one think about results that depend on AC? I just encountered this:

"(Theorem of A. H. Stone) Every metric space is paracompact... Existing proofs of this require the axiom of choice...
  It has been shown that neither ZF theory nor
  ZF theory with the axiom of dependent choice is sufficient"

I understand that it's standard to mention whenever AC is used to prove any results. I also read here on this site that it is due to the fact that undesired stuff like the Banach-Tarski paradox happens when you assume AC.
My question is, as a non-set theorist, how should one think about results that depend on the axiom of choice?
I'm sorry if this question is too broad but please realize that part of the reason I'm asking it is because I'm not sure what is the real question here...
ADDED: There's a great thread on MO on that very question!
 A: It depends on your philosophical bent, really. And what can't tell you how to think about things philosophically. You need to learn enough and figure it out on your own.
The axiom of choice is a tool. But it is a magical tool, like the summoning of Satanic, or Divine, or non-Judeo-Christian good/evil dichotomy related spirits. 
Okay, I digress. The point of the axiom of choice is that it allows non-constructive results. It allows us to prove the existence of objects without specifying their exact "form". To some people it bothers, to others it bothers less.
What does it mean that a result depends on the axiom of choice? It really just means that with the usual foundation of $\sf ZF$ set theory we cannot point out at the objects that will prove that result (e.g. a choice function, or a well-order, or a basis for a vector space). 
Of course sometimes we can prove limited and partial results without the axiom of choice. In fact, often we can prove the results that we want for well-behaved enough spaces (where "enough" depends on the result, of course). But assuming the axiom of choice allows us to prove much more general statements which are much easier to state. Let me give you an example.

Theorem. ($\sf ZF$) Suppose that $K$ is a field, and $K$ can be well-ordered, and suppose that $V$ is a vector space over $K$ such that $V$ can also be well-ordered, then there is a basis $B$ for $V$.

On the other hand...

Theorem. ($\sf ZFC$) Suppose that $V$ is a vector space over a field $K$. Then $V$ has a basis.

So it really just helps us to clean out a lot of assumptions which may or may not be true for spaces that we are interested in, and make them true in a broader and nicer generality. Since mathematics progresses towards infinitude, this is a good thing.

One last remark on the Banach-Tarski issue, which I often bring up, is that if we assume that all sets are Lebesgue measurable and the Banach-Tarski theorem fails, then we get something equally even more disturbing. There is a partition $P$ of $\Bbb R$ such that $|\Bbb R|<|P|$. That is, there are strictly more parts than elements!
How 'bout that for paradoxical?
A: Math is a collection of creative games which together involve millions of players across the world and spanning all of human history. A subcollection of these games is called set theory. The most popular set theory game is called ZFC. ZFC has several popular relatives, one of which is ZF and one of which is ZF+DC. What you've stated is this: when playing the ZFC game, "metric spaces are paracompact" is a legal move. When playing the ZF game or the ZF+DC game, it is not a legal move.
In applications, these kinds of things tend not to come up. In most cases, something you need for an application can me proved without choice, but you may have to prove it in a more restricted setting and it may be more difficult to do so.
