Hunter-gatherers eating traditional diets had very low rates of the modern "diseases of civilization" including cancer, heart disease and diabetes. When, however, hunter-gatherers switch to eating modern diets they start getting these diseases at high rates. (Of course this correlation doesn't prove causation, but still...) Also, anthropological evidence from bones show that populations usually became less healthy after adopting agriculture.

Although hunter-gatherers had lower life expediencies than we do, this was mostly due to them dying of stuff (murder, infections, viruses) that doesn't significantly reduce the life expectancy of Americans. The paleo lifestyle tries to combine the health virtues of modern day and paleolithic man.

I look at paleo as providing Bayesian priors for the health value of different foods. If food X was eaten for a million years by my ancestors whereas food Y was eaten for less than 20,000 years then my prior belief is that food X is probably healthier than food Y. This seems to be the implicit approach taken in the Perfect Health Diet. The value of paleo priors is inversely proportional to the strength of nutrition science.

Forgive me for not having citations to backup these arguments. They are based on my readings of the secondary paleo literature.