Temp was cold at last couple nights, ~35. When car fully warms up I turn on the heater, because my toes are about to freeze off. Drive around a little and look at the temp guage and the car is almost totally cold again! WTF...was does that mean?

 

It means your damn lucky... but i would be sure the car is actually cold and its not just the gauge telling you it is

 

You wanna check your thermostat, see if it's malfunctioning.. If it is it could also be not reporting the higher temps too, which would keep your fans from coming on if it heats up and may lead to overheating.

 

It'd be a VERY good idea to replace the T-stat now, it sounds like it isnt staying open. i had the same problem on my protege, and it was the t-stat not opening/staying open.

 

I'd say your one lucky SOB