The point is that the shifts suggested by the paleo dieters aren't necessarily in the direction of truly ancestral diets.

First, as we agreed, there were many different "truly ancestral" diets. Second, it depends on the starting point. I will assert that if you start with a typical American diet, eating most any kind of paleo will shift you in the right direction. We can argue about starches and such, but it's pretty clear that no one ate large quantities of grains or seed oils 100kya, not to mention all the processed food-like substances :-/