This is the quote I was thinking of when I wrote about the time period of
the optimal human diet: "Living organisms thrive best in the milieu and on
the diet to which they were evolutionarily adapted; this is a fundamental
axiom of biology." (O'Keefe JH Jr, Cordain L. Cardiovascular disease
resulting from a diet and lifestyle at odds with our Paleolithic genome: how
to become a 21st-century hunter-gatherer.  Mayo Clin Proc 2004
Jan;79(1):101-8. http://www.mayoclinicproceedings.com/inside.asp?AID=651&UID
http://www.thepaleodiet.com/articles/Hunter-Gatherer%20Mayo.pdf)

HOMO SAPIENS IDALTU DATES BACK TO AT LEAST 154,000 YEARS AGO
My memory was off on the date of the origin of Homo Sapiens. The earliest
known subspecies of anatomically "modern" Homo Sapiens--Homo Sapiens Idaltu
(meaning "elder")--has been dated back to 154,000 to 160,000 years ago
(http://www.cbsnews.com/stories/2003/06/11/tech/main558166.shtml) and some
scientists speculate that Idaltu originated around 200,000 years ago.

HOMO SAPIENS MAY HAVE CONTINUED TO UNDERGO SIGNIFICANT CHANGES UNTIL AS
RECENTLY AS 40,000 - 70,000 YEARS AGO
Adding complexity to this is the view of some scientists who believe that
Homo Sapiens was still experiencing significant genetic changes until 40,000
to 70,000 years ago (I've also seen the figure 50,000 bandied about), when
it finally evolved into the current subspecies Homo Sapiens
Sapiens--behaviorally modern humans. So it's difficult to nail down a narrow
time period within which Homo Sapiens were eating the optimal diet for
today. My guess is, any of the food categories from which H. Sapiens
commonly ate between 200,000 and 15,000 years ago would be fairly optimal
(which I understand to be meats and organs, seafoods, vegetables, fruits,
nuts and seeds, and herbs and spices). 

COOKING STILL HAS BEEN AROUND LONG ENOUGH FOR DIGESTIVE ADAPTATION
So if you accept only the most cautious estimates of when cooking became
widespread (around 125,000 ya), it doesn't predate the origin of
anatomically modern humans, but it still allows plenty of time for humans to
have adapted to digesting cooked foods.