Tad,
There are various cuisines which lend themselves quite easily to paleo eating... look at North African [leaving the couscous out], particularly Moroccan... many Mediterranean cuisines, Middle Eastern and Thai too, can all be easily tweaked to fit with paleo principles... even some deserts form those places are essentially paleo :-)
Dedy
From: Tad Glines ... << I have a really limited set of recipes right now and it does make it harder to stay on track when my choices are so limited>>