Sounds like you have a serious cooling system problem! I've never found
adequate heat to be a problem even at -20 F in the Ur-q, though adequate heat
at -20 F can be a problem in the 4KQ. Perhaps you have some type of obstruction
or the "new" thermostat is bad. I run a 160 F thermostat and an appropriate
radiator fan switch in the Ur-Q and the heat is still excellent. You might want
to check that little control valve in the heater-core supply line, if the cable
is out of adjustment your flow through the core would certainly be reduced.