I don't think exercise is necessary for fat loss, no, but it definitely helps for retaining muscle mass and promoting good metabolic effects. The type of exercise is important as well. But when people are just starting out and need to drop (say) 30+ pounds of fat, ANYTHING they do proactively for their health will give them an improvement in the way they look.
If I were a trainer, I'd recommend that people add one healthy habit per week. Doing Tabata circuits would be in my top 10 recommendations, because they're an easy habit to get into. Low time commitment, high results. And if Tabatas are the ONLY habit someone adds to an otherwise crappy lifestyle, they will see plenty of rewards right away.
Of course, by that same logic, doing Mercola's Peak8 would work just as well.
Nick: I don't think it's unhealthy to go for 7 minutes. That IS a long time to be sore, but soreness actually has to do with the amount of calcium ions floating around in your muscle tissue, having been released by the tearing of muscle fibers. The ions "irritate" muscle fibers that haven't been exposed before (or not in a long while), which is what leads to the soreness (kind of a black box process as far as I can understand it). The "deeper" the exercise, the more muscle fibers get irritated, but they adapt over time, which is why the next time you do the same sort of exercise, you don't get as sore (or not sore at all).
It's possible that your low-carb diet was too low to enable quick repair of the cells such that they built up defenses against this irritation. If you felt extra tired during this recovery time, then, yeah, it's probable.
Here's an article talking about what Delayed Onset Muscle Soreness is and how it works:
Dave: That's interesting! You've given me good motivation for eliminating those last few inflammatory foods that have been lingering in my diet. I hate the "upper arm flab" I've been watching grow since I hit, oh, age 25 or so.
What's the toxin-binding protocol you use?