Well there are the clinical trials, which can be found by searching "paleolithic diet" in pubmed; they're generally positive. They're on the "orthodox" view of the paleo diet espoused by the first wave of paleo advocates. It's generally low in fat compared to what we do, is pretty good for the metabolic syndrome. Although many people around here eat more fat, more starch, and more dairy, just because they don't find problems with those things. Eating like a hunter-gatherer from the paleolithic era is just the template and starting point, it's what we are supposedly best adapted to, what is well entrenched in our evolutionary history and from most of our experience it's pretty fail-safe. That doesn't mean that we don't find out that we are well adapted to something after all 10000 years later. And it doesn't even mean that the orthodox paleo view was 100% right about what was eaten. Was the human diet really low fat and without starch for so long? There are a lot of paleo diets from different groups who mixed genetically after all.

Studies:

http://www.ncbi.nlm.nih.gov/pmc/articles/PMC2724493/?tool=pubmed This one sould have gone on for longer, since the "paleo diet" is improving with time whereas the "diabetes diet" is getting worse. Then again all diet studies should go on for a longer time but there's the $$$$ to think about.

http://www.springerlink.com/content/h7628r66r0552222/fulltext.html This one only demonstrates a benefit from a paleo diet, not that it has shown to be better than a "Mediterranean diet" here, because that's not really what people call a Mediterranean diet.

http://www.ncbi.nlm.nih.gov/pubmed/17522610

There are probably a few others, but those are the main ones. There should be more studies coming out in the next few years.

There is Anthony Colpo's post on grains. Not paleo but anti-grain. http://anthonycolpo.com/?p=852 I'll just leave it up to people to read it critically and decide for themselves.

However science doesn't really work like you suggest. It's not like bam study in yo face, how'd you like my now, my dietary paradigm is valid! Just because a "paleolithic diet" fares well in a study doesn't mean that any particular tenet is truth. They made sweeping dietary changes and improved health, but usually there is little we can say other than about the whole, unless we get seriously good food reporting and do a linear regression analysis of different factors to go along with a large population size. That's money. Even better would be a dozen different groups all completely controlled, but, well, $$$$$$$.

It would probably be best for them to just start learning about health in general with an open mind. How terrible would that be? What I would do is just say "Look, if you want to learn about health science, go ahead and I'll discuss individual points with you open-mindedly. Find out what the evidence supports on different individual points and keep proportioning your beliefs to the evidence forever and ever." Not to be reductionistic; interactions between different dietary changes count to, it's all very complex and the big picture is beyond me, but not so much beyond other people on this site who will probably chime in with their take.

All of the major blogs are worth looking into. I'm not going to argue for a "paleo diet" because I'm not married to a paleo diet, it's just that I eat in a similar way most of the time and the paleo community is where a lot of the action is.

I know that you just want information and some of the scientific basis for what we believe, but questions as broad as that cause me to ramble. I don't apologize for posting a disjointed answer!

Not categorically paleo but these are great articles and pretty damning -

"The western diet and lifestyle and diseases of civilization"

http://www.dovepress.com/the-western-diet-and-lifestyle-and-diseases-of-civilization-peer-reviewed-article-RRCC

And

"In the face of contradictory evidence: report of the Dietary Guidelines for Americans Committee"

http://download.journals.elsevierhealth.com/pdfs/journals/0899-9007/PIIS0899900710002893.pdf