I suspect the controller board in the furnace has a loose wire somewhere. Until you can get someone to look at it you can try getting the thermostat to run the fan with the heat, often called an "electric heat" setting.
Furnaces will commonly use different circuits for starting the fan motor depending on the thermostat settings, there will be a circuit for continuous fan operation (often at a lower speed), a circuit for heating, and possibly another circuit for cooling. With the fan always on the fan will already be spinning if there is a need to heat and so bypasses whatever electrical issue there may be in spinning up the fan for heating. It could be a failing motor bearing or capacitor, those can show as intermittent problems too. Replacing the motor doesn't mean you got a good motor to replace a bad motor, maybe you got a lemon.
What might be a fix, at least temporarily, is to program your thermostat for "electric heat". This will be a setting in an electronic thermostat, or a switch or jumper hidden inside a mechanical thermostat. Electric resistance heating often relies on the thermostat to signal turning on the fan, not a controller in the furnace. There's a long explanation on why this is that I won't go into (and another long story on how I figured this out) but in most thermostat manuals it's often called an electric heat setting and not explained what it does. Some manuals will explain what this setting does, or call the function something else. Either way if the thermostat can run the fan but the furnace can't then telling the thermostat to run the fan with the heat is a way around this, again at least temporarily.
I find it odd that you say the fan blows loud in "fan on" mode, that should be the low speed setting in a dual speed fan. The installer might have some wires crossed, this may be another sign the furnace controller is bad, or again a lemon fan motor.
Addendum:
The fan running fast in "fan on" mode may not be so odd after all, after giving this some thought. The thermostat will control the fan for the air conditioning and that will be at a higher speed than heating, selecting "fan on" at the thermostat is closing the high speed fan circuit. Whether you have electric heat or fossil fuel heat doesn't change the function of the "electric heat" setting in a thermostat, that's just telling the thermostat to close the fan circuit with the heat. If there is air conditioning that relies on the thermostat to run the fan then the fan control wire will be wired for high speed. Even though "electric heat" selected in the thermostat could be running the fan at high speed during heating this would be preferable to not running the fan at all. I offer this option as a temporary fix to get through a night, weekend, or whatever to avoid an emergency service fee from HVAC repair services. Just leaving the fan on all the time is another option but that will introduce noise, and a bit of a chill with the air moving and the furnace is not running. On more than one thermostat I've seen this "electric heat" setting is a switch behind the cover, just pop the cover off, flip the switch, pop cover back on. This is simple, requires no tools, and easily reversed after repairs are complete.
