I'd say it's a combination of increased investment in your goals and, more importantly, a better hormonal environment that makes primal foods more palatable. It's not as if we came up with these restrictions arbitrarily, there should be a synergy between the kinds of foods we want to eat and what our body craves. After expending valuable energy and nutrients, the body wants something nutritious. Also, for some people at least, the experience of craving cookies is often driven by misplaced emotional eating or simply tiredness. After vigorous exercise, with your metabolism humming long after the session to repair and recover your muscles and supplies, you generally feel good and alert. And if you do get tired you're more likely to sleep rather than find yourself stuck awake in zombie-sugar land in front of the tv.

There is a balance though - if you take too much out of yourself then you can end up grabbing the nearest calories available and if you're not used to a paleo diet then that may be a big pile of fries. I use it as one of the signs of overtraining, when I start needing carb heavy recovery meals just to be able to walk the rest of the day.

What He said ^^. I find when I really focus on dialing in my diet, my training improves, and vice versa. You are committing more of your mental energy to your health, and all aspects of health will benefit.