I use a similar nutrition regimen, but not quite so restrictive as paleo. I encountered a lot of paleo enthusiasts in the Crossfit community. I basically follow something close to the Zone diet with some sensitivity to paleo principles I guess is the way to say it.
I am not 100% strict in this, but I try to stick to it 80-90%
I avoid refined/processed carbohydrates. I try to get 2/3 or more of my carbohydrates from colorful and/or leafy green vegetables, and one third from select fruit (grapefruit, berries, apples, occasional oranges, etc.). Relatively little from legumes or starchy vegetables. I go out of my way to consume "healthy" fats (nuts, olive oil, fish oil, avocados, etc.), and I go for moderately lean animal protein (although with the way the cost has spiked lately, this is a shrinking facet of my diet, and I'm relying more on turkey and eggs). I don't avoid dairy, but I wouldn't call it a staple either. So it winds up being similar in marco- and micro-nutrients to paleo. I'm not real precise with quantities but it's probably pretty close to an even split between calories from protein, carbs, and fat, but the carb calories are probably lower than the others.
I've been doing this for 4 years. It allowed me to get off statins, lose/maintain weight, cured acid reflux, and greatly reduced the effects of seasonal allergies.
Every now and again I still break down and get a pizza or a cheesecake or a blueberry pie.