the valve on the firewall (under the hood, passenger side, heater hose from engine goes in one end, and other goes into car to heater core) may not be opening all the way.
http://www.supras.com/06/techcenter/display.php?QID=67
Just read and do A. & B. Don't bother with doing C.
You do NOT need to replace a bad solenoid, just by-pass it and plug the vacuum line directly into the water valve.
The system 'normally' keeps the valve open (water flowing), all the time, except when the temp is set to 65*.