I had some initial issues (mostly GI) after first switching to a more paleo diet, but at that time I was eating quite a bit a fruit (but still lost a ton of weight).
For the last few days I've been VLC, and I've felt great. I'm gonna keep it up to see what happens.
I've had this nagging suspicion that most of the benefits that come from low-carb diets are actually just the result of removing refined sugar (basically the truly enormous amounts of fructose in the SAD), wheat, and perhaps other grains and legumes. As far as I know this has not been tested, but, anecdotally, many people seem to be able to lose tons of weight without being VLC. Also, even mister VLC himself, Dr. Kurt Harris, has changed his position and now believed that carbs are not what matters, but rather excessive fructose.
People talk about metabolic derangement, but as far as I know the evidence that the solution to this is low-carb, as opposed to low-fructose and gluten-free, is not particularly strong- though I'm certainly open to being corrected on this.
Also, I've heard that consuming wheat elicits a similar physiological response to opiates, so that would suggest addiction, and therefor withdrawal, is an issue with wheat. Certainly it seems like many people are seriously addicted to wheat.