I've yet to see any evidence on the effects of calorie restriction on humans. Mice are quite different from us, and all evidence on calorie restriction I've seen was done on mice.
Evidence on humans can be found through here, and extensive discussion on evidence in macaques can be found here (although I recommend reading the whole discussion and/or the study; the root comments are less informed than the leaf comments).
I recently came out against paleo in the open thread, and realized that I probably haven't yet heard the strongest arguments in favor of a paleo diet. So, what are said arguments?
EDIT: Or more generally, why should I eat less carbohydrates and more protein / fat?