The other time I noticed losing a lot of weight pretty easy was when I was in the habit of making a huge shake for first meal, like, an entire blender full of psyllium fiber, raw eggs, protein powder, frozen fruit, and maybe yogurt or something, and drink the whole thing at once. Got down to a size 6 then.
Currently I am somewhat overweight, size 11, but I notice I will not lose weight if I do not consciously deprive myself somewhat of calories. Diet is not ideally primal but doing more and better at it over time. I've only been really interested in primal since late last year. I'm really good at maintaining my weight, and not gaining any, but losing it is hard, and haven't been able to get below the current weight for probably 6+ years now. I do NOT calorie count at all, I hate that; I just keep in mind in general how much I have eaten for the day. And if I eat normally, without any deprivation, I maintain weight. But it seems I do need to deprive myself at least somewhat to lose any weight; as in, don't go for another meal late in the day, and just in general restrict myself from eating a bit more than I would prefer. I'm still in the process of getting grains out of my diet, and most days fail at not eating grains, but I do make an effort to eat less, and am currently eating a lot less than before. Unfortunately, I still have a good stock of various "healthy" grains in the house that I bought before I got with PB, and I really hate to waste things, so there they sit.
In short, while my diet is not totally primal, it's better than before, but losing weight is definitely not effortless.
A conscious, moderate amount of calorie restriction is still necessary to lose weight.