I replaced the thermostat, and the temperature guage shows the engine coming to temperature within a few minutes. But the heater doesn't blow heat for quite some time (45 minutes or more). When the heat finally does come, it's fine and seems pretty normal.

Any suggestions as to what's wrong - thks

Sounds like your cooling system could use a good flushing and that your heater core could be plugged up. Did you have this problem before you replaced thermostat? If ans. is NO, check that thermostat was installed correctly, domed side up...sorry but had to be sure. If YES, flush entire cooling system, install backflush kit.