Originally Posted by mults

To me, it sounds like air in the system. Even if the thermostat is stuck open, the coolant should still be warm-ish. If there is heat when driving and none when you stop, there is not enough coolant to reach the heater core.

My $.02...but either way, take it back and get them to fix it...Let us know what they find.