My girlfriend and I are about 85-90 percent Paleo (I believe in the basics, just don't think one has to be a zealot about it). I'm more of a "creator" in the kitchen myself, but she likes having a recipe to follow, so we've used the following Paleo cookbooks for inspiration:
- Well Fed
- Well Fed 2
I also have gotten recipes online from Primal Palate and PaleOMG.
That's what I got off the top of my head.