The air is too cold.
too much cold air is getting through the engine radiator cooling it too much, blasting your engine effectively causing it to be air cooled. Does your temp guage ever get up to operating temperature? If it doesn't then you should block some of your radiator with some cardboard so it will warm up normally. Running an engine that is too cold can cause increased wear.
The cold outside air needs to be warmed even more by your heater block, but this colder air is moving at the same speed as the normal temp air was. If your cooling system is getting up to proper operating temperature, and your heater block was able to warm 60 deg normal air by 20 deg giving you a warm 80 degrees, the cold 45 deg air would only get to 65 deg. These are all hypothetical numbers but the principle is the same. If it can only heat the air by x it will not be able to heat it any more than x.
Try recycling the air inside the car rather than using outside air. This will take the luke warm air inside and keep increasing the temp adding more heat each time it went through the heater core.
Either way the windows in the car are the main source of cooling the air inside the car. This means even with recirculating the air the heater core will need to battle the heat loss from the windows.
If you have a mix of all three of these issues it will just make the problem worse.
One more thing you can do is set the fan to a lower setting giving the air more time to heat up it may not make the car hot but it may warm you up a little more.