This happens to me, too. Even when temps are above freezing, things can freeze to the canister (like your fingers -- be careful!) As the canister cools, of course, the inside pressure drops and you get reduced output, so using an upright canister stove in cold weather is sort of a double whammy.

The putting-the-canister-in-water trick goes back a ways, and it only has to be liquid water, it doesn't have to be warm. The water keeps the canister from cooling off too quickly.

The other trick is to take off your gloves, blow on your hands, and wrap them around the canister while the stove is burning. You get an immediate increase in pressure and output. You also get really cold hands.