Let's drill down:

• millet bread isn't paleo
• rice protein powder isn't paleo
• gluten-free ginger snaps are probably made of rice flour, and thus aren't paleo

Now I'm not going to say that everything I eat every day is perfectly paleo, but if your sample menu has this many grains/processed foods on it, you're not going to be headed in the right direction.

The best thing you can do right now is tough it out and fill out your diet with real foods. There is absolutely no reason to be eating bread, and I agree with Travis that you should maybe up the meat intake here at breakfast. Or consider adding veggies...tossing a scramble over some spinach, etc. is tasty.

Instead of doing a pre- and post-workout snack, try working out a little bit hungry and then eating a more substantial meal afterward...and not a liquid one, one made of actual food. If you want to lean out, don't drink your calories.

Dinner looks pretty good, but instead of the ginger snaps (hard to give up, I know) maybe try to look for a more paleo sweet, whether it's fruit and nuts or a custard. I do funky things like slice up half a banana and top it with a mix of 2 parts full-fat Greek yogurt to 1 part almond butter or sunbutter, topped with walnuts and cinnamon. Glorious.

You're getting there...just try to eat more foods that look like something you could get from nature.

It looks pretty good overall, but it seems a little low on meat for my tastes. I generally skip the nuts and snacks and things and just eat 2-3 large, satisfying meals. The breakfast I just ate consisted of 4 eggs fried in pasture butter with 3 strips of turkey bacon and 1 small purple potato steamed and then buttered. I end up not having to eat for a long time afterward and can feel less tethered to food in general.

When you make a hard shift away from carbs and nuts, you don't really need to count calories. Apples are pretty high in fructose, and millet bread doesn't sound optimal.

That all being said, you may very well reach your goals with this diet given your activity level, but if you hit a plateau, you may want to reexamine a few of the details.

Brad,
It looks like you're doing great so far. Your macronutrient ratios look good. If you're dissatified with your rate of fat loss and muscle gain, the suggestions I would have are:

1) You may need to increase your energy intake. An active, 100+ kg person may need 3000 to 4000 calories per day. If you starve yourself chronically, you may eventually lose more muscle than fat.

2) Eat less frequently, and give your body a chance to dip into those fat stores. Consider intermittent fasting (discussed in depth on previous threads).

3) Be careful of overtraining with P90X (or any crosstraining program). If you overtrain, you increase your stress and cortisol levels, which can inhibit fat loss.

Good luck!

I think I went through a pretty similar transition phase, where I'd eat more almond flour cake and nuts and fruit rather than just eating meat, eggs, vegetables and coconut oil. You're doing pretty well but how about introducing more neat and particularly organs- eg liver or heart etc? If you're not ready for that ease into it slowly and experemt at your own pace, but I'd say pass the man chops and breadcrumb free sausages for now! ;)

Also, as I said in a comment above, fat is GOOD. Don't drain your bacon, eat all the fat on the meat, eat spoonfuls of coconut oil, throw egg yolks in a smoothie or just fry them up post workout... You get the idea. Melissa over at Hunt Gather Love is great to read on the topic of fat. You'll also find yourself much more satiated and will crave that millet bread and almond snaps much less.

I tend to take the desire to snack as a sign that I'm not doing something right. I definitely eat more calories (esp. breakfast -- 3-4 eggs, much more meat, veggies, coffee with cream) than you, and I'm 5'6"/160 and less active. A late breakfast like that takes me through til dinner.

Gluten free sweets/'bread' if you tolerate them well are a reasonable once-in-a-blue-moon cheat once you've got yourself on track but shouldn't be a regular part of meals.

It also took a while to break myself of the habit of needing dessert. It sounds like you might be in the same rut. Making sure you eat til you're full can help with that too.

+1 on the suggestions of intermittent fasting. I never imagined I'd be able to do it, but the more satisfying, real foods I ate (and NO grains), the longer I could go between meals.

Not to be down on you... you're obviously well on the way and eating better than most of the population, but some further improvements could really help :)

Strictly speaking, butter and cream and bacon are all non-paleo. Paleo is about lean meats, which bacon definitely is not. If you do eat bacon, try to get nitrate/nitrite free. (That said, I have cream in my coffee every day.)