Heating controller “thinks” it’s too warm and brings cold air

[fmugur]

The temperature controller is set to 70F and it works fine for while, like 10-20 minutes or less, I couldn’t figure out why it varies. The outside temperature is very cold, somewhere around 0F. Suddenly, the controller switches to cold air, “thinking” that inside is warmer than 70F. I go up to 80 and the fan spins faster bringing more cold air in. Again “thinking” the inside is very warm. So, no matter where I set the temperature, the system brings cold air inside. Up to here you may think it is the thermostat or air in the system but here is the trick. When I get the temperature up to 90F then I get heat. It seems to me that when I set to the max it does not care about temp sensors and it opens up the valves to let the coolant to travel through the core heater. I thought at the beginning that there is the temp sensor or little fan inside the controller and I opened it up and cleaned it. Before to put the unit in I also checked to see if it spins and it does. I cleaned the thermoresistor / sensor that’s in front of the fan as well.
I had no luck debugging this problem. I don’t know much about how the system works but I would count on your help to figure out what could cause this problem which is very annoying. The work around is to let it set for 90F and keep adjusting the fan speed which does not work very well since the airflow is dependent on the car speed as well.
Do you know if there are other sensors that I might need to check? I got it to the dealer and they want to replace everything like thermostat, valve controller, hoses, coolant temp sensors and a lot more up to $3000.

Thanks in advance for your help.