That is a hypothesis and should never be treated like anything more. We are genetically identical and thus we MIGHT not be adapted to our new diet. You can still be adapted to things that you have never seen before. Being able to metabolize lactose was lucky because all it took was persistence of an infantile trait into adulthood, more or less. Our gut flora actually produce some ethanol so that was already there. While we're more or less identical (would we really say exactly identical?) there has been much natural selection of pre-existing genes.
The thing with grains is that it is their biological niche to poison anything that tries to eat them. To be able to adapt to lectins and such we would need some pretty profound evolution and I don't think it has happened. That doesn't mean that we haven't adapted a bit, some have somewhat of an adaptation to gluten, just not enough to make it a healthy food, probably. The conclusion is a bit of a truism, we haven't adapted to our new diet because sufficient adaptation hasn't taken place.
We always need empirical evidence to back these claims and I don't think anyone really takes pure paleo logic as a valid conclusion unless tested for. If they do then they shouldn't. That a good way to be wrong about stuff.
Stabbing conventional wisdom in its face.
Anyone who wants to talk nutrition should PM me!