OK, here's something I wrote up for a friend. These are rules of thumb, so if you see something that doesn't apply in some circumstance, you're probably right.

Typical backpacking type fuel canisters consist of three gasses: butane, isobutane, and propane.

Each of these fuels vaporizes at a different temperature: butane at 31F (-0.5C), isobutane at 11F (-11.7C), and propane at -44F (-42.1C). If you deliver the fuel as a gas, it has to vaporize before it reaches the burner. If the outside temperature is lower than the vaporization point (boiling point) of your fuel, your fuel won't vaporize (it'll stay liquid), and your stove ceases to function. You can shake your canister and hear fuel sloshing around, but your stove is, quite literally, out of gas.

As the temperature declines and you pass each one of those vaporization points, you lose one of the components of your pressure and as the canister empties you also lose pressure just from the reduced amount of fuel. Also, because propane has the lowest vaporization point, it has the highest pressure and burns off faster than the rest. In other words, in cold weather your best fuel gets used first, and only your lower performing fuels are left toward the end.

All three of these things contribute to "canister fade," increasingly reduced efficacy as the canister approaches empty.

You've got a few choices:
1. Keep the canister warm, but you'll still have canister fade toward the end, and in really cold weather, keeping the canister warm is either difficult or dangerous (depending on the technique employed).
2. Switch to a liquid feed gas stove. You're still using the same three fuels (butane, isobutane, and propane), but they're fed in as a liquid, and the burner is doing the vaporization, so the outside temperature isn't as big of a deal.
3. Go with liquid fuel (white gasoline or kerosene).

Here's Hikin' Jim's general temperature range recommendations:
40+ F Gas, Liquid Feed Gas, or Liquid Fuel will all work well.
30F - 40F Gas, Liquid Feed Gas, or Liquid Fuel will all still work, but you're going to start to notice degraded performance on gas.
20F - 30F Gas, Liquid Feed Gas, or Liquid Fuel will all still work, but you're going to notice degraded performance and you're going to have to use tricks on gas with many gas brands toward the low end of the temperature range.
10F - 20F You're getting below where regular gas stoves operate. If you're headed out in this kind of weather, do your self a favor and upgrade to a different type of stove. Yeah, if you fiddle with it enough, you can get your regular gas stove to work, but basic tricks don't work well down this low, and more advanced tricks are dangerous. Dangerous as in severe injury or death.
0F - 10FThis is simply below the operational range of ordinary gas stoves. This is where liquid feed or liquid fueled stoves rule the day.
-10F - 0FNo way in heck on regular gas stoves. Even liquid feed gas stoves can have trouble as you approach -10F. Specialized liquid feed gas stoves like the Coleman Xtreme will handle the cold better.
< -10F Liquid fueled stoves only.

OK, so there you have it. Those are "rules of thumb" and are a general guideline only. No guidelines can cover all circumstances and conditions. Those are guidelines that are going to work fairly well at most elevations. If you're going above 15,000', feel free to adjust the numbers as needed.

All of the above are ballpark numbers at best. So much depends on other things like wind, how you use the stove, what tricks you employ, how full is your canister, which brand of gas you're using, how sheltered a spot you're in, are you cooking in a tent or out in the open, etc.

HJ