I recently mentioned a study showing that dietary intake of fiber from grains was strongly tied to lowered risk of death from cardiovascular, infectious, and respiratory diseases, and also protective against cancer deaths in men. (That intake would have to be mostly from whole grains, since the whole point of refining grains is to remove the fiber-rich bran.) And I mentioned that this was another strike against the "paleo" diet, which strongly discourages consumption of grains, as well as legumes and tubers.
Followers of the paleo fad argue that their diet is optimal because it represents what humans ate before the development of agriculture. But as it happens, for years we've had evidence that consumption of wheat and barley -- and perhaps even grain-flour bread -- goes back at least 23,000 years. (And there are hints that it might go back as far as 105,000 years, but that's still very speculative.)
And more recently, in an analysis published in the Proceedings of the National Academy of Sciences researchers from George Washington University and the Smithsonian Institution examined phytoliths (microscopic bits of silica or other minerals from plants) and starch grains found on Neanderthal teeth dating back 36,000 to 46,000 years. Their research shows that these most iconic cavemen (who have been recently shown to be part of our ancestry and not just an evolutionary dead-end, as was argued for some years) were not only eating legumes and grains like barley, but were cooking these carb-rich foods to improve their digestibility. (Full article here, though it may be hit by the copyright cops at some point.)
Paleo advocates ask us to accept two propositions: 1) that a diet similar to that eaten by our pre-agricultural ancestors is necessarily optimal for health, and 2) that the diet they advocate is similar to what paleolithic humans ate. But the former claim stems from a fundamental misapprehension about evolution; the latter, from bad anthropology and bad archeology.
Evolution does not care about your individual health. If you survive long enough to have kids, and you (or someone else in your tribe) are around long enough to care for them until they're able to fend for themselves, natural selection is done with you. And so natural selection does not optimize heavily -- in many ways evolution's motto is more like "good enough is good enough" than "survival of the fittest".
An old joke: two guys are out camping, and spot a bear charging towards their campsite. One of the campers starts to take off his hiking boots and put on running shoes. "What are you doing? You can't outrun a bear!" says the second guy. "That's okay," says the first guy. "I don't have to outrun the bear. I just have to outrun you." Natural selection is like that -- the first guy's ability to run is "good enough".
The ability to survive on a wide variety of foods diets is obviously of evolutionary advantage. It's why roaches, rats, and humans have all done well -- we can live off of whatever is available. But as far as evolution is concerned, "live off of" is enough. Once it had hacked the digestive system of our primarily fruit and leaf eating ancestors to be able to survive on a wide variety of foods -- partly via the use of external organs of digestion, namely tools and fire -- that was "good enough"; beyond the minimum needed to pass on your genes, health and longevity are outside natural selection's bailiwick. So knowing what paleolithic man ate is not very informative regarding the question of what the most healthful dietary practices for modern humans are.
As for the question of what the actual paleolithic diet was like, we see that the archaeological evidence does not support the "paleo diet" claims. So from where did these claim arise? Much of it comes from extrapolation of contemporary hunter-gatherer tribes. But many of these societies are in fact displaced agricultural people, not hunter-gatherer cultures surviving from ancient times. And most have been pushed out to marginal environments, because -- as it happens -- agriculture and civilization are very successful patterns of being human.
These factors alone would cast doubt on the extrapolation of these groups' diets back to paleolithic times. But more than that, the data we have about these tribes was not generally collected by researchers trained in dietary collection techniques, and was mostly collected by men -- who, either out of their own pre-feminist notions or out of tribal taboos, often did not associate with the women who typically do the gathering half of the hunter-gatherer lifestyle.
Our picture of hunter-gatherers is very skewed -- as is evident by the name by which we call them. "Gatherer-hunters" would be much more accurate, but the mythological place of hunting is strong. The diet of the !Kung, for example, is about 67% plant foods; the Hazda get the bulk of their food from wild plants, including getting about half their food just from starchy tubers, although they live in an area rich with "game" animals and refer to themselves as hunters.
To its credit, the "paleo diet" does urge people to cut back on sugar and dairy and processed foods. Certainly the paleo diet is less unhealthful than the high sugar, high fat, low fiber atrocity that is the Standard American Diet. And most paleo advocates are advocates of exercise. But it's not as if "eat less sugar and junk and get some exercise" are new and unique insights.
The paleo diet has little to do with how our paleolithic ancestors actually ate, is not nutritionally optimal, and is not an ecologically sustainable way to fed billions of people.
And it doesn't deal with the fundamental ethical issue of killing our fellow sentient animals.
All of these considerations still recommend a diet based on whole plant foods, including grains, legumes, and tubers, rich in complex carbohydrates and fiber.