The former. The latter interpretation didn't even occur to me, although now that you mention it I can see how if you were a fan of the paleo diet you would interpret it that way. That's interesting, it is certainly possible it was the latter but it seems unlikely.
I'm still not sure I buy the double meaning interpretation either. pg probably meant to imply only one of the interpretations. He writes pretty clearly and directly. I think the former is much more likely, since that's the simplest interpretation of the sentence and it's accurate. The paleo diet is new (to avoid any argument from paleo fans it doesn't actually have much to do with what paleolithic humans actually ate, so it's not old in that way).
As I see it, it's pretty clearly the latter.
I didn't notice this double-meaning the first time around. As a fellow reader of the essay, do you think pg is implying that the Paleo diet is new or that it's a reaction to new food? First time reading it I assumed it was the latter, now I'm leaning to it being the former.