I haven't lost or gained weight. My workouts haven't been much worse or much better. I don't notice a difference in energy levels, although I find it harder to ignore hunger now. My major impressions are that a paleo diet is expensive and inconvenient.
This is just my experience. The scientific arguments that I've seen made follow the general pattern of this article: neolithic foods contain chemicals (e.g. lectins, phytates, etc.) that are bad for our bodies.
These kinds of arguments are extremely unconvincing. Digestion and metabolism involves thousands of chemicals and reactions. Trying to piece together how it works is important, but a couple isolated components are not nearly enough with which to make judgements for your health.
Arguments from personal experience are even worse. If you "feel better" on the diet, are you sure it's the diet? Is it the placebo effect? Is it the fact that you are likely eating more fiber and nutrients? Is it a difference in blood sugar levels that you notice? Even worse, is the advice to cut out foods, and then test how those foods make you feel when reintroduced. Any change can easily be interpreted negatively. Also, your body has adjusted to the new foods (which quite likely caused their own painful adjustment period).
Good arguments would make actual health claims, such as 1. The chance that you develop heart disease will fall. 2. The chance that you develop cancer will fall. 3. The diet will prevent some other diseases (e.g. diabetes). 4. Some specific symptoms from some specific diseases will lessen.
Currently, this whole fad seems like a big echo chamber of people seeing exactly what they want to see.