If you're sure it is linked to the cold weather, then have you noticed anything else like - for example - that the engine temp gauge is slower to come up to operating temp. Or maybe the heater is least effective when on the move. Anything like this might suggest a thermostat problem of some sort (stuck or even missing).
If airflow through the matrix is blocked with flies, I'd expect disappointing airflow even when fan on setting 4 (and assuming fan is rotating freely, another easy one to check) but anyway neither of these would suddenly appear with a change of season I think, and nor would a blocked water matrix.
But I'm no techie so maybe someone else could comment.
