Here is a link (happened to be the first one I found) that refutes the no grain part of the paleo diet. Take that one with a grain of salt as I just cannot find the actual link to the paleontologist who discovered either grain starches or pollens in the dentin of recovered teeth from a paleolithic site in Canada. I will continue looking though.
http://thespartandiet.blogspot.com/2010/10/its-official-grains-were-part-of.htmlRegards,
Bill