I've read the paper more closely and I think I understand it somewhat better.
The paradox in the paper is actually closely related to the comments with which I concluded my earlier message. What they are saying is that if we are part of a Poincare recurrence, it is overwhelmingly likely that the past is false. And worse, it is overwhelmingly likely that the past is inconsistent; that we were or are on a trajectory that could not be continued all the way back to the Big Bang. That is because the entropy at the time of the Big Bang was very low compared to today, so the vast majority of today-like worlds have no plausible continuation back to a Big Bang. The specific example they give is, what if the cosmic microwave background was 10 degrees rather than 2.7 degrees? If we think about a Poincare recurrence in the process of forming, time running backwards, a hotter than usual microwave background will not cause any problems. You could still get planets being un-destroyed, life becoming un-extinct and running backwards, etc. Eventually you get back to the present day. And we look around and see a universe that's at 10 degrees. That's a big problem. There's no way our universe could have formed from a Big Bang if the microwave background was that hot. It means the Big Bang was completely different, we wouldn't see the elemental abundances we see today, galaxies wouldn't have formed properly, and so on. We would see a world which was inconsistent with its putative past. Yet we don't. Broadly speaking we seem to live in a universe to which we can ascribe a reasonably consistent model of the past. This contradicts what we would predict if we lived in a Poincare recurrence, hence we probably don't. Now you might say, so what, the whole idea that we formed in this way was so absurd that no one would ever take it seriously anyway. But the authors of this paper seem to be saying that if you assume that there is a positive cosmological constant (as the cosmological evidence seems to show), eventually we will get into this de Sitter state, and based on some assumptions (which I didn't follow) we really should see Poincare recurrences. Then by the anthropic principle we should be overwhelmingly likely to be living in one. Hence there may be something wrong with our cosmological theories. Another point, Tim is of course right that the time for one of these recurrences to happen is enormous. The formula they give is t = exp(S1-S2), where S1 is the entropy of the equilibrium state, which they estimate as 10^120 for the de Sitter universe, and S2 is the entropy of the state we are going to chance into, which they say would be about 10^10 for time near the Big Bang. So this means that the time until something interesting happens is about exp(10^120). The authors comment, "This seems like an absurdly big time between interesting events, which by comparison last for a very short time. Nevertheless dismissing such long times as 'unphysical' may be a symptom of extreme temporal provincialism." As far as the de Sitter model, the references I have found agree that it has rapid, exponential expansion, with no beginning and no ending, and that it is a "steady state" model of the universe, which looks the same to all observers at all times. However some authors say that it has no matter, and others say that it has a constant density of mass-energy, and I'm not sure how to reconcile that. In this paper the authors do a coordinate change where the de Sitter model can be considered to have a constant volume and density, so that sooner or later recurrences should, well, recur. Hal Finney