Binnie asked for top 5 recommended books. Back i june last year I wrote
to this list about some books on hunter/gatherer life (not very much about
diet, but still I think worthwhile reading to broaden ones thinking around
paleodiet and its original context, also some of it amusing).
So I cite myself here, with some small changes:

Some easy reading about h/g life:
* Marjorie Shostak: "Nisa, the life and words of a !kung woman" is a
true story from the inside of the !kung people of Kalahari.
Earthscan publications ltd  ISBN 1 85383 060 7
* Kenneth Good: "Into the heart, An amazoninan love story". The author
spent most of ten years in a Yanomama village, an got married there.
His intention was in fact to gather knowledge of what the Yanomamas ate,
and collected a lot of material on this, but sadly lost all his
notations in the rapids of a river.
Very amusing to read about when his wife and her brother are brought
directly from the stone age to modern Caracas.
Penguin  ISBN 0 14 016643 2
* Jean Liedloff: "The continuum concept" The author spent two and a half
years with Yekwanas, and tells us about a very happy people. Much about
child-rising. Has a "paleo-diet" approach to psychology or one would
rather say that paleo-diet is the food side of the continuum concept.
(I have only the ISBN for the swedish edition of this book).

(Yanomamas and Yekwanas are not pure hunter/gatherers, they are partly
gardeners, Yekwanas probably mostly. Yanomamas regularly leave their
village for a couple of months, going foraging and nomading in the
djungle.)

Some more pure scientific reading:
Tim Ingold, David Riches, James Woodburn, editors: "Hunters and
gatherers"
(two volumes) Berg publishers  ISBN 0 85496 734 6 and ISBN 0 85496 735 4

-Hans