"It cannot be shown without some form of AC that the union (or disjoint union) of countably many countable sets is countable. I have a countably infinite set X of countably infinite sets. Therefore, the union of X cannot be shown to be countable without Choice."
The fallacy is that in many cases of interest, it is possible to exhibit an explicit counting of every element of X. In such a case a counting of X by antidiagonals is easily constructed. The usual counting of the rationals is an example of this.
I think this may even be an example of a more general phenomenon of "people think AC is necessary for a certain construction, but in fact it turns out not to be necessary for the example they have in mind". For example, AC is necessary to find a maximal ideal in an arbitrary ring ... but it isn't if you're prepared to assume the ring is Noetherian.