A nice paradox (in the sense of going against the common opinion) which is not in that list is Arrow's theorem. More or less, it states the following. Let be given a set of people who vote on some issue, and have a finite number of alternatives (at least 3). Each person orders the alternatives according to her preferences; the outcome of the vote is an order on the set of alternatives which is supposed to reflect the common consensus.
More formally, a preference is a total order on the set of alternatives, and a voting system is a function which associates to each $n$-uple of preferences another preference. It turns out that the only voting system which satisfies some innocent-looking hypothesis is the projection on some factor, that is, the dictatorship of one of the people.