Would the fan come on, but the air was cold, or did it just do nothing at all?

If nothing at all, I'd look into the cold engine lock. Basically the climate control has a separate temperature sender on the thermostat housing (there are three there...) that tells it when the coolant is warm enough to turn on the heater. In my experience these usually fail on, so the heater comes on too soon and blows cold air on your toes.

If the fan came on and blew air out the footwells, but was not warm, then I would check the coolant level to see if it is low. Also look into a potential problem with the heater valve. Disconnecting power to the heater valve normally permits full heat, so removing the connector from the valve makes for a quick test.

You'll get heat without an operating recirculate pump, just not quite as much of it.

- JimY