There are a couple reasons. First of all, it's important to note that the sensation of warmth or coolness is only indirectly related to temperature. The receptors in your skin that deal with temperature are mainly sensitive to heat transfer and changes in temperature, not so much absolute temperature values. For example, here's an interesting excerpt from the EB article on thermoreception:
Cold receptors respond to sudden cooling with a transient increase in
discharge frequency (called the dynamic response) that is directly
related to the prior temperature and the magnitude and rate of the
temperature decrease. If the cooler temperature is maintained, the
discharge frequency adapts to a frequency of static discharge that is
directly related to the cooler temperature.
So the sensation of coolness has to do with how quickly heat is being transferred away from the skin. Heat transfer occurs in three modes: radiation, conduction and convection. It's that last one that's important, because convection relies on motion; with no motion, there's only radiation and conduction. Air is a pretty good insulator, making conduction less effective; and it's transparent across a wide spectrum, meaning there's no significant radiative heat exchange. And your skin has many tiny hairs (and perhaps larger hairs, depending on the person) that work against any minor convective flows, as from a draft or small disturbance.
Basically, in the absence of convection (moving air), your skin will locally warm the air right around itself, and that air won't be very quickly replaced by cooler air. As it warms, it conducts even less heat away from your skin (because the smaller temperature differential is a weaker driver).
But the much more significant factor in most cases is probably increased evaporative cooling. Just as that layer of air around your skin conducts heat and is warmed by your skin, it also evaporates moisture and becomes more humid. (Your skin can always lose some amount of moisture to dry air, even if you don't feel sweaty.) Just as heat transfer will be reduced as the air warms up and approaches your body temperature, so too will evaporation be reduced as the air immediately surrounding your body gets slightly more humid. But when the air is moving, it gets much more effective at evaporating moisture from your skin. You can read about the mechanism of perspiration for some more background.
In both cases, the moving air acts relatively more like a constant-energy sink because as your body contributes heat energy and/or moisture, those higher-energy molecules move away from the interface with your skin and are replaced by more cool, dry air. From an analytical perspective, if the air is moving quickly enough you don't have to account for it getting warmer or more humid over time as it exchanges heat and moisture with your skin.
As this comment points out, it's important to recognize that while perspiration is specifically a cooling mechanism, convection works both ways; if the surrounding air is warmer than your skin, a breeze will make it feel even hotter. If you're really interested in this topic, UC Berkeley's Center for the Built Environment has a neat thermal comfort tool that you can play with, which goes into much more detail as far as individual and environmental variables.