In the comments to the linked article there's a nice explanation by Terry Tao of why this is not so spectacular, in the sense that our intuition with probabilities here relies on Fubini's theorem, which in this case do not apply due to measure theoretic obstacles. But, again, our intuition of probability fails with much easier examples.
Here follows Terence Tao's comment (refer to the original to have proper rendering of math symbols):
"This paradox is actually very similar to Banach-Tarski, but involves a violation of additivity of probability rather than additivity of volume.
Consider the case of a finite number N of prisoners, with each hat being assigned independently at random. Your intuition in this case is correct: each prisoner has only a 50% chance of going free. If we sum this probability over all the prisoners and use Fubini’s theorem, we conclude that the expected number of prisoners that go free is N/2. So we cannot pull off a trick of the sort described above.
If we have an infinite number of prisoners, with the hats assigned randomly (thus, we are working on the Bernoulli space {\Bbb Z}_2^{\Bbb N}), and one uses the strategy coming from the axiom of choice, then the event E_j that the j^th prisoner does not go free is not measurable, but formally has probability 1/2 in the sense that E_j and its translate E_j + e_j partition {\Bbb Z}_2^{\Bbb N} where e_j is the j^th basis element, or in more prosaic language, if the j^th prisoner’s hat gets switched, this flips whether the prisoner gets to go free or not. The “paradox” is the fact that while the E_j all seem to have probability 1/2, each element of the event space lies in only finitely many of the E_j. This can be seen to violate Fubini’s theorem – if the E_j are all measurable. Of course, the E_j are not measurable, and so one’s intuition on probability should not be trusted here.
There is a way to rephrase the paradox in which the axiom of choice is eliminated, and the difficulty is then shifted to the construction of product measure. Suppose the warden can only assign a finite number of black hats, but is otherwise unconstrained. The warden therefore picks a configuration “uniformly at random” among all the configurations with finitely many black hats (I’ll come back to this later). Then, one can again argue that each prisoner has only a 50% chance of guessing his or her own hat correctly, even if the prisoner gets to see all other hats, since both remaining configurations are possible and thus “equally likely”. But, of course, if everybody guesses white, then all but finitely many go free. Here, the difficulty is that the group \lim_{n \to \infty} {\Bbb Z}_2^n is not compact and so does not support a normalised Haar measure. (The problem here is similar to the two envelopes problem, which is again caused by a lack of a normalised Haar measure.)"