The two that come to mind are splitting epics in Set and taking the Skel of a category. Surely there are lots of other interesting (and maybe upsetting) places where this comes up.

$\begingroup$ I community wiki'd this. It's borderline for mathoverflow anyway (see the FAQ), but for now we're allowing "sorted list" discussin questions. They do have to be wiki'd, however. $\endgroup$ – Scott Morrison♦ Oct 31 '09 at 18:37

1$\begingroup$ I find it slightly odd to say that splitting epics in Set is a place "where the axiom of choice crops up in category theory". The existence of splittings for epics in Set is the axiom of choice. $\endgroup$ – Tom Leinster Aug 28 '12 at 0:01
Using the usual definition of "functor," almost any functor constructed using only universal properties requires the axiom of choice. For instance, if a category C has products, then one wants a "product assigning" functor C×C → C, but in order to define this you have to choose a product for each pair of objects. If C is a large category, then you need an axiom of choice for proper classes.
However, this sort of thing is arguably not a "real" use of the axiom of choice. It's more accurate to say that in the absence of the axiom of choice the usual definition of "functor" is not sufficient, and one must use anafunctors instead. Proving that fully faithful + essentially surjective = equivalence is the same. Most often in category theory when we want to "choose" something, that thing is in fact determined up to unique isomorphism (though not uniquely on the nose) and in that case using anafunctors is sufficient to avoid choice.
The axiom of choice does, however, come up in the study of particular properties of the category Set. One interesting consequence of the fact that epics split in Set is that all functors defined on Set preserve epics. I think this is an important part of Blass' proof that the existence of nontrivial (left and right) exact endofunctors of set is equivalent to the existence of measurable cardinals. Another interesting consequence is that Set is its own "ex/lex completion."
In proving that whenever there is a full, faithful functor F: C to D which is essentially surjective (i.e. hits every isomorphism class of objects in D), C and D are equivalent categories.
(This is pretty close to your example of taking Skel of a category.)

$\begingroup$ The nlab page on anafunctors (ncatlab.org/nlab/show/anafunctor) says that this is actually equivalent to AC. $\endgroup$ – Ketil Tveiten Aug 28 '12 at 8:28
While not the traditional Axiom of choice, Zorn's Lemma makes an appearance on the road to Mitchel's Theorem;
If X is an abelian category with the sup property(Grothendeick's AB5), then an object E is injective iff it does not have a nontrivial essential extension.
Mitchel's theorem is stated in Rotman's Homological Algebra(page 316) as;
If A is a small abelian category, then there is a covariant full faithful exact functor from A to abelian groups.
I believe(but do not have access to the appropriate materials to give details) that Zorn's lemma appears in homotopy limits also.
If $s:\mathcal{X} \to \mathcal{C}$ is a fibered category and $\varphi:C \to D$ is a morphism in $\mathcal{C}$, for each object $y$ in the fiber $\mathcal{X}_D$ the axiom of choice allows us to specify exactly one pullback $f:y_C \to y$ (i.e., a cartesian arrow $f$ with $s(f)=\varphi$). The choice of such a collection is called a 'cleavage', and a cleavage always exists by the axiom of choice.
This enables us to define the 'change of base functor' $\varphi^*:\mathcal{X}_D \to \mathcal{X}_C$.
Choosing fiber products to define the sheafification of a presheaf with respect to a grothendieck pretopology (you later prove that this construction is independent of choice, but it's necessary during the construction). See stacksgit in the remark immediately preceding proposition 8.10.3.