Re: Problem with Paleo (+Diet Critique)
Even eating "Paleo" (which, to reiterate what others said, does not include dairy), you still need to have a caloric deficit to lose fat. Fortunately eating a caloric deficit comes a lot more easily on a paleo diet, especially when you cut out things like processed bread/breakfast cereals/poptarts and the like and replace with whole unprocessed carbs, protein and fat. Since the "average" person is first cutting a lot of empty calories and then replacing them with fat and protein, they're very satiated and thus end up losing weight. HOWEVER - if you're still taking in more than maintenance calories on Paleo, which is definitely possible especially if you're eating lots and lots AND LOTS of fat, you'll gain weight.
I also suggest cutting out the milk.