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.