Anecdata: I have lost over 30 pounds since switching to a vaguely paleo (but really more carb avoiding) styles of eating last december. I track my weight daily, and cheat on saturdays, except a couple weeks ago when I cheated for the whole of Gencon. Very reliably, I gain weight after Saturdays, and gained 9 pounds over the course of Gencon. I tend to lose weight after days that I do not eat carbs on, and my lowest weight for a given week is almost always on Saturday morning. I do not track calories at all.
IIRC most weight gain/loss over very short periods of time (e.g. one or two days) is usually due to water weight. So if you gain weight only on one day of the week, it's probably just water.
I recently came out against paleo in the open thread, and realized that I probably haven't yet heard the strongest arguments in favor of a paleo diet. So, what are said arguments?
EDIT: Or more generally, why should I eat less carbohydrates and more protein / fat?