Did you have the belt done at a shop or did you do it yourself?
Was the thermostat replaced and if so did you use a Toyota Thermostat or aftermarket one?
Perhaps the system was not bled correctly?
Normally when we do anything with the cooling system we do the following when bleeding the system:
- Put the heater on full temperature (no Auto)
- Set the blower to the lowest setting
- Run the engine until its nice and toasty and the thermostat opens (I use an IR thermometer to see that the two hoses are about 20~30°F of each other)
- Optional- Use a stick or brake pedal depressor to set the idle around 2,000~2,500rpm for about 5minutes to make sure everything is nice and toasty
The procedure above is how we normally get most if not all the air bubbles out of the system. I personally use the following tool when bleeding the system as I feel it is the most efficient manner and allows you to observe bubbles:
Post Note-
I would also check and see if the interior temperature sensor is not dirty. Its that little guy behind the slotted vent under the ignition switch dash kick panel.