I went off paleo for a year or so, now back on for a few months and have gone from 178 to 162 lbs. without doing much else than cutting out sugar, gluten grains and plant oils. It's strange this time; when I occasionally eat these things, I feel slightly, but noticeably ill for about a day afterwards.
Anyhow if this type of diet interests you, I want you to check out his blog because it is a slightly different approach than other "paleo". You need not eat super low carb as long as it is the right type of carbs and you don't have a ton of weight to lose. He also suggests cream if you don't have leaky gut (I drink tons in coffee every day).
These are a couple tidbits from his entry on glucose: http://www.archevore.com/panu-weblog/2011/2/5/no-such-thing-...
"Glucose is a necessary internal fuel source and metabolite and it is also a food and the building block of foods that have the longest evolutionary history of any food that mammals use. It is a fact that we do not require glucose in the diet, and that we can make it from amino acids if we don't eat it. However, rather than viewing this as evidence that glucose is not important, we should view this as evidence that glucose is so metabolically important that we have evolved way to make sure we always have it." ...
"Like glucose, there is no dietary requirement for fructose, but unlike glucose, we do not require fructose for use as an internal fuel. There is no organ like the brain that has an absolute fructose requirement. In fact, our body has mechanisms that evolved specifically to keep most cells from being exposed to too much of it." ...
"To keep fructose out of the general circulation, it must be immediately burned or stored as fat. Fructose is related to the spectrum of serious diseases known as NAFLD (non-alcoholic liver disease), including fatty liver and cirrhosis."