Why a fan make us feel colder instead of warmer in a cold room?

First of all, that is not a definition of heat. Heat is energy transfer due solely to temperature difference. What is described in your post is more like a definition of internal energy (kinetic and potential energy at the microscopic level).

The reason you feel colder with the fan on is the movement of air over your skin increases the rate heat transfer from your skin by increasing the convection heat transfer coefficient. The relevant equation is Newton's law of cooling

$$\dot Q=hA(T_{s}-T_{∞})$$

Where $\dot Q$ is the heat transfer rate, $T_s$ is the skin temperature, $T_∞$ is the bulk air temperature of the air away from the skin, $A$ is the cross sectional area of the skin, and $h$ is the convective heat transfer coefficient. The faster the air moves the greater $h$ is, all other things being equal. In effect, the air movement forces the air close to the skin to carry heat away increasing the efficiency of heat transfer to from the skin to the air.

You've probably heard of the "wind chill factor". For a same air temperature the wind increases heat loss from the skin making the air feel colder than when there is no wind.

Thank you for the answer, that definitely helps, just one question, do we ignore the motion of air molecules due to fan movement because it's too small, negligible and fan is not rotating fast enough? or the fan moving the air in a cold room never creates any heat even in microscopic levels, no matter the speed of the fan?

Keep in mind the fan does not "create heat". Heat is energy transfer due to temperature difference. I think what you are really asking is if the fan can increase the temperature of the air molecules because the fan increases the velocities of the air molecules. It is possible that the fan could slightly, but not measurably, increase the temperature of the air by "stirring up" the air molecules, since the temperature of the air is a measure of the average translational kinetic energy of the air molecules. But the fan motor coil, which gets hot when the motor is running, would probably have a greater effect on the air temperature.

Hope this helps.

The still air near your skin has higher humidity that the air that the fan brings into contact with your skin; the drier air promotes evaporation of moisture from your skin. Your body provides the latent heat for this evaporation, hence you cool off.

After reading Bob D's answer, I would say both increased heat transfer from convection and evaporation are important. You can consider both effects by increasing the heat transfer coefficient in Bob D's formula to consider evaporation. (To be technically accurate, evaporation is mass transfer from the body to the air, not really heat transfer, but its effect can be lumped into the heat transfer coefficient. See, for example, the classic McAdams Heat Transmission textbook.)

In addition to the (by now) two great answers, what we perceive as heat/warm is in most common situations caused by random movement of the air molecules.

You are correct to think that the increased kinetic energy of the air molecules (caused by the fan) should transfer more energy to your skin, thus increasing the perceived temperature. As mentioned by Carl Berger, this is basically the same process that makes spaceships re-entering the earth's atmosphere heat up - there is relative motion between the object/observer and air particles in both cases.

However, as explained by John Darby, a uniform particle flow (which is caused by the fan or wind, for example, causes a chilling effect, thus cooling the perceived temperature.

If the particles move randomly (as in "normal" air without wind), the random movement of the individual molecules (approximately) cancels out and doesn't cause a windchill effect. They however still transfer energy to your skin, so increased movement will lead to a higher perceived temperature.

In summary, the increased uniform movement particle does transfer more energy to your skin, but the cooling effect that it causes is stronger, so in total, you feel a drop in perceived temperature. If there is no wind (random particle movement), the chilling effect doesn't happen, which means that higher particle movement equals higher perceived temperature.