The sets don't have to be countable; if there are continuum-many of you indexed by the reals from 0 to 1, the angels could match the interval from 0 to 1/6 with the interval from 1/6 to 1. However, doing this does not preserve measure (as jimrandomh pointed out above), which is the real sleight-of-hand that makes this thought experiment akin to the one where everyone who rolled a six gets unwittingly duplicated up to five copies.
It's only if the sets are countable that we can probabilistically predict ahead of time that there is a pairing. To get the existence of a pairing, we need to know that the cardinality of those who rolled six is equal to the cardinality of those who didn't. It is a consequence of the Law of Large Numbers (or can be easily proved directly) that there are infinitely many sixes and infinitely many non-sixes. And any two infinite subsets of a countable set have the same cardinality. But in the uncountable case, while we can still conclude that there are th...
I saw this conundrum at Alexander Pruss's blog and I thought LWers might enjoy discussing it: