Several comments, which I hope may help.
The Coleman fuel is 70% butane and 30% propane. This is fine for warmer weather, and will work in cold weather , but I would recommend using a fuel which was 70% ISO-butane and 30% propane. Many other brands offer this.
Reason: Butane boils at -0.5 C (~31 F). Iso-butane boils at -12 C (~11 F). The lower boiling point helps. But propane boils at -40 C (-40 F) or maybe a little lower even, so a liquid-feed canister stove can work down to nearly -24 C as the canister will be pressurised. Warm the canister up a bit and it is fine at even lower ambients of course. Me, I might not be so fine at -40 F though ... :-)
Added by edit: why won't the canister work down to -40 F? Because the higher vapour pressure of the propane is diluted by the presence of the butane. Both the Powermax and the Kovea 30%propane/70%isobutane will kark at around -24 C (about -10 F) when the internal pressure drops to about one atmosphere.
I have used the MSR WindPro myself in the snow with an inverted canister, and I found that the valve sometimes blocked up exactly as you described. Annoying. I was able to clear it every time by opening and shutting the valve at least half a turn each way. Cook, wiggle, cook, wiggle ...
What is causing this valve problem? I don't know. The canister does contain a small amount of a smelly chemical to warn you of leaks (often a mercaptan), and possibly this was gunging up at the valve, or even freezing around the valve. The Fyrestorm and the Xtreme do not do this in my experience - no idea why not!
Note: this problem is completely different from the problem people have trying to use an upright canister stove in the snow. In that case the butane stops boiling and the propane gets used up fast, eventually leaving almost pure butane.
You are welcome to look at http://www.bushwalking.org.au/FAQ/FAQ_GasStoves.htm
where I have a lot more info about gas stoves and so on. Not part of BPL - I wrote these pages before I joined BPL, but maybe they will help too.