WJM,
We had the exact same problem Monday on our '93 Loyale here in Toronto, Canada. Just like you, cold outside temperatures, especially with the wind chill (under 0F). I drove it all day yesterday and could bearly get any heat out of the blower in the cabin. It wasn't freezing air blowing in, but it certainly wasn't warm. More like 'cat breath' warm... good for nothin'!
When I had a chance, I checked the coolant level (low coolant level is well known in our car to cause the heater core to blow cold air) -- coolant level was perfect.
So we took it to our very trustworthy mechanic here in Markham (he's worked on all our Subarus, not a dealer) and he found it: it was the thermostat. It had probably been in there for 5+ years and I guess it was just old enough so as to open it's valve at too low a temp., and the engine never got a chance to fully warm up 'cause too much cold water was being allowed into the system from the radiator.
We've had a lot of cold days up here lately, and non of them ever caused this problem. He put in a new stock thermostat, and wholla! Problem solved.
The heater now pumps out the serious heat I've grown accustomed to expect from all our Subies, and my toes are warm once again. Subaru heater cores have always impressed me with the amount of heat they pump out, so I wouldn't settle for anything less than "ahhh, nice and warm!" even in the dead of winter at 0 degrees F.
Hope that helps -- get your thermostat replaced. But first, make sure your coolant level is filled up to the brim, and make sure there's no air pockets in the upper and lower rad hoses (squeeze 'em with rad cap off, and engine running -- but do it when it's cold to prevent scalding!).
Best of luck,
-badrasta