Why does moving air feel colder? If temperature is just the average kinetic energy of particles, why would moving air feel colder rather than warmer?
 A: As a thumb rule, one feels cold when the skin loses heat to the ambient. 
Still air (at temperature lower than that of skin) extracts heat from your skin by free convection between skin surface & near by air molecules this results in rise of temperature of nearby air molecules but when air starts blowing the hot air molecules near your skin is displaced by incoming fresh air molecules. This results in faster rate of heat (forced) convection between your skin and blowing air. This make you feel blowing air colder rather than warmer. 
Also the reason why you feel stagnant air hot is that hottest molecules of stagnant air remain in contact with your skin in free convection mode of heat transfer.
A: The premise is wrong that moving air feels colder in general. It is applicable for temperatures up until about body temperature. If you are for example in a Finish sauna (dry sauna) you have temperatures around 75–100 °C (167–212 °F) where if you blow on your skin you will get hot and even burn yourself.
A: If the air was still, body heat warms a thin layer of air next to the skin. This warm air would stay near the skin, separating it from the cold air. Wind, however, continuously blows away this warm bit of air, replacing it with the colder surrounding air. There's a similar effect on humidity. Evaporating sweat increases the humidity right next to the skin, decreasing the rate of evaporation. Wind removes this humid air and replaces it with the less humid surrounding air. This is why a fan can cool a person down by blowing hot air at them.
I've also heard stories from soldiers driving tanks in the desert that remaining still can make 120$^\circ$F (49$^\circ$C) days more tolerable. Their bodies create a layer of 98$^\circ$F (37$^\circ$C) air next to their skin.
A: Only up to the certain convection effect bound. When convection effects stop, imagine you would move around with speed of 300 meters per second. This speed is not so difficult to achieve. Surrounding air will start to "heat" you up.
In the boundaries between speed of sound $C=330$ m/s and kinetic speed $V=1000$ m/s of air (by the formula from kinetic theory $V = \sqrt{2 kT/m}$) your temperature will be growing.
At the speed exceeding $V$, air particles will strike at you, then being reflected back with greater speed, making you to heat even more. Your temperature will rise up to the point when you start glowing, emitting radiation to cool yourself. You will become a meteorite.
A: You can't feel air temperature, you feel rate of heat transfer
Your body has no sensors that can measure air temperature directly - the only thing that you can sense is the temperature (and its relative change) within your skin. 
This may seem a technicality - after all, a standard thermometer also measures not the temperature of air but the temperature of the thermometer - but there is a substantial difference because the thermometer is expected to match the outside temperature and your body is not.
Furthermore, your body is continuously shedding heat through your skin; and since it's an important body function (you will die if it can't do that), the "heat sensors" we have are quite good for the purpose of estimating how fast you're losing heat and if that rate needs to be changed through regulating sweating or constriction of blood vessels.
So what you're effectively measuring through your "feeling of temperature" is not the temperature, but the rate of heat loss through your skin. All other things being equal, it correlates with temperature as in cooler environment you lose more heat than in a warmer environment. But as soon as anything significantly increases the usual heat conductivity away from your skin such as the difference between still and moving air, or the difference between touching wood or metal at the same temperature - it's going to cause an exaggerated feeling of temperature; cold moving air will feel colder than cold still air; hot moving air will feel hotter than hot still air; cold metal will feel much colder than cold wood and hot metal will feel much hotter than hot wood - all this because you don't feel the temperature of the air or the things you touch, you feel only their effect on the internal temperature of your skin.
A: TL;DR
In windy conditions, the air surrounding you is replaced more rapidly.
Why Does Moving Air Cool You Down?
Heat is Energy Transfer

There are a few different important factors to consider. Starting with the fundamentals, heat is the transfer of energy. When you "feel colder" your nerves are sensing a change in temperature, generally due to the transfer of heat from your skin to the surrounding air.
There are three basic ways that energy can transfer: conduction (physical contact), convection (fluids, like air, swirling around), and radiation (like sunlight). While the other two will be operative in some way, the one affected most by wind would be convection. Low wind speed means that the air close to your body will be replaced by the surrounding air gradually. High wind speed means the air is replaced more rapidly. However, the effect will be different depending on the characteristics of the surrounding air. 
Cold Moving Air Disperses Warmth

If the surrounding air is colder than your body temperature, then the wind causes colder air to replace the air close to your body more rapidly. This will reduce the average temperature close to your body. The greater the temperature difference, the faster the energy transfer.
fast cold air -> fast energy transfer away from you -> you feel cold
slow cold air -> slow energy transfer away from you -> you feel less cold
Hot Moving Air Promotes Evaporation

Your body works hard to regulate its temperature to keep it within a very narrow range. The primary mechanism it uses is sweat. Your pores release water. Through conduction, energy is transferred from your skin into the water. When the water absorbs enough energy, it undergoes a phase change, becoming water vapor. Eventually, the air nearby starts to become saturated, the evaporation process slows down and sweat pools up. In order for the evaporation to start again, the humid air close to your body will need to be replaced by drier air further away from your body. Also, if the air is humid, then even fresh air will become saturated very quickly. 
slow (or humid) hot air -> slow evaporation -> skin feels wet and warm
fast (or dry) hot air -> fast evaporation -> skin feels dry and cool
Is "Moving Air" Warmer?
There are two different kinds of speed to consider: microscopic/particulate speed, and macroscopic/aggregate speed. If temperature is based on kinetic energy, it would seem fast-moving air is hotter than slow-moving air. However, extending this reasoning to non-fluids shows the problem. A car traveling 90km/h in Antarctica will not be hotter than a car traveling at 5 km/h in the Gobi Desert. A more precise, definition of temperature is "microscopic mean kinetic energy." The microscopic part is important. A car's center of gravity may have high kinetic energy, but if the tiny particles that make up the car aren't moving much relative to their surroundings, then they are not very hot. It's much messier with fluids, but the principle still applies. Picture a school of fish. Individual fish might be moving slowly compared to the other fish, while the school is moving quickly. This is kind of like cold, windy weather. Or, individual fish might be moving quickly compared to the other fish, even though the school itself is moving very slowly. This would be kind of like hot, not-windy air. It's kinetic energy in both cases, but it only counts as temperature if it relates to microscopic movement, not macroscopic movement.
A: There are many answers that are physically correct already. The full explanation is however slightly more complex, as it's not only a physics thing.
You do not feel the cold per se, nor do you feel heat transfer (that was stated in another answer, but it's not the case for all we know). Thermal receptors come in two flavors which are typically idle, non-responsive in the 30-35°C range. The one interesting here is the one for "cold".
The receptor is basically the end of a neuron (where some instable molecules have a certain half-life time according to how warm it is, blah blah), and the neuron internally measures the concentration of these (well, not really, second messengers change ion gradients, which adjusts the potential difference on the membrane up to eventually triggering, but, whatever, that's nitpicking).
This particular type of neuron behaves in such a way that it is inert above its threshold temperature, which is normally approx. 30°C. If the skin's temperature (and thus the temperature of the receptor) drops below that, it starts firing, the faster the lower the temperature, reaching its maximum at approx 20°C. Normally, temperature is not perfectly constant, but quite so. Also note that these neurons develop a very significant tolerance to stimulus, so a "mostly kinda constant" state is indeed "constant" from the neuron's point of view. This is why sudden changes are perceived very thoroughly whereas constant cold eventually isn't cold any more (even though it really is), and slow changes are not noticeable either.
Fun fact: A similar effect exists in many places, e.g. with many drugs, including alcohol. The actual amount of alcohol certainly matters for being a poison, but it matters very little for feeling drunk. It's the sudden change that matters. If you drink very slowly, you can literally drink until you drop dead from poisoning. If you "help" resorption by e.g. adding carbon acid, and shoot it on an empty stomach, you can get stinking drunk from a single drink.
In normal conditions, the skin is warmer than the threshold because of the explanations given in a different answer: There is a thin insulating layer of air which is slightly warmer (and also, air isn't terribly good at taking up heat anyway). Sweat doesn't evaporate very well either if the nearby concentration is high (which it is). The blood stream delivers new heat slowly but steadily (mostly), and the environment only takes up so and so much, which results in a balance within the normal "indifferent" range.
Moving air ("wind") does away with all of the above. It disturbs the protective insulating layer, it introduces new (usually, but not necessarily slightly colder) air, so the gradient is a bit larger (heat loss is proportional to surface, a material factor, and the temperature gradient!), and that air possibly (not necessarily!) is less saturated on water, too.
In other words, wind is indeed cooling (as long as the air temperature is lower than the temperature of the to-be-cooled thing). Heh, wonder why computers have fans. Also, you gotta wonder why it gets hotter (at least apparently!) in the sauna when you swirl the towel instead of getting colder. It's the same thing, only in reverse.
Wind is also rarely a steady, laminar stream, but rather a changing, unsteady, chaotic thingie. That may very well cause the receptor's tolerance to be much slower to kick in than it would/should normally be (the receptor being much more sensible to changes, and different receptors being stimulated at different moments).
Thus, the skin's temperature drops below threshold, and the neuron starts firing. At some point, it doesn't get worse, that is when the lower threshold is reached (20°C is quite nastily cold -- doesn't sound like it, but consider that's not surrounding air temperature, it's living tissue temperature!).
Eventually, if temperature is low enough and there's still life within, noziceptors (pain emitting) kick in and take over, which is why extreme cold can be (but needs not if the limb is numb) just as painful as heat while you do not actually feel cold any more, just pain. It's one of the reasons (reperfusion being the other) why warming up again can be quite painful, too.
A: In addition to Mark H's answer, if your skin is moist the breeze will evaporate water, producing a cooling effect.   
A: Temperature is defined this way in the KINETIC theory of gases, i.e motive energy of point masses where there is a LOT of reason to think that in reality effectively ALL that can be known by measuring the effect of one fine grain of gas on any other (Potential energy) is known and no thermodynamic information will be gained by further looking ever closer. In this case you may want to pursue mathematically that temperature size is an average because directions may be just random (Which makes a lot of common sense as well).
If this is the coarse nature (Where there is experimental motivations for the concept of coarse graining in the analysis) of motion then trivially you will not feel it moving you (You are not a grain in a gas for that matter, right..?). More accurately if your body feedback by resisting to movement of gas then you are the grain of another gas (If you enter the atmosphere in ever growing free fall then you are the a thermodynamic thing, and not so much the atmosphere itself) and the motion is in a far larger scale and is effectively uniform in direction. You feel it is colder because it has a lower temperature than the grains that constitute yourself and the flux is trivially bigger when the wind is faster and a greater amount of cold grains (slower on average on hitting grain of yourself) since momentum is conserved in every pair hitting then they gain some and you lose some and this is why you feel air is cold or hot. If the air was warmer then a faster wind would heat you and cool the air.
The phases of matter are immaterial to answering what was asked. As usual the thought should be in the correct direction. Not just in elementary physics but especially in it. You sweat because your body gains temperature from air hotter than yourself. The liquid of sweat is reacting with radiation slamming into (The quite surprised) outer gas and it is guaranteed to in this case further heat the surrounding gas and so the sweat uniformly cools down. This is why we bring supplies of water with us when going to the desert. Remarkable.
A: Another complicating effect is The joule-Thomson effect which explains the temperature change of a REAL gas as it is forced past an obstruction.
https://en.wikipedia.org/wiki/Joule–Thomson_effect
A: Temperature is the dispersion of velocity, and does not depend on the average flow velocity. Whether or not there was wind, the temperature does not depend on this. Otherwise, in another inertial coordinate system, the temperature would rise to a large value.
