That's pretty interesting. I'm no neuroscientist, but I don't think the idea that exercise leads to better cognitive performance requires an assumption of minimal brain evolution since pre-agrarian times. The pathways by which exercise is thought to exert its effects are quite low level: brain oxygenation, modulation of cortisol levels, etc. I imagine it would take a rather dramatic evolutionary jump to change the response of brain cells to oxygen levels (but again, I'm no biologist).

The studies Medina cites in his Google talk (I've only read bits and pieces of his book) are pretty compelling.