One of the main claims revolving around the paleo diet is that it is 'unnatural' foods, i.e., foods that are incongruent with our evolutionary past that cause us to eat excessively and become fat.
From an evolutionary perspective, the ability to gain weight when food is plentiful is a survival trait. It is necessary to stay alive in circumstances where food isn't always plentiful and readily available, i.e., nature. Now lets suppose that a low carb diet is congruent with what our bodies need from an evolutionary sense. Why wouldn't we be able to gain weight (add fat) on the food that humans normally ate for thousands of generations? Why would that survival trait, the ability to store energy in the form of fat by overeating, only work for the kinds of foods that we didn't encounter very often (carbs)? If anything, it seems like we ought to be highly optimized to store fat in the face of abundance when eating the paleo way. After all, who knows when the next wooly mammoth might be bagged!