I spent a lifetime trying to lose weight but finally did so keeping carbs low. I also found that to some extent, calories do matter. I don't believe it is possible (at least for me) to eat primal without also keeping my calories in an appropriate range for my height. Exercise in any form helps as well. I started at none and have increased in increments as my body became more able. As someone else suggested, tracking calorie & carb intake as well as calorie expenditure might give him the key.
Starting Weight: 197.5
Current Weight: 123