KC: My experience differs from yours regarding canister stoves.
bobmn:
I don't think the OP is referring to canister stoves. My understanding is that the term canister stove refers to small backpack stoves such as an MSR Pocket Rocket or Optimus Crux or Snow Peak Gega. They burn Isobutane which is a blend of butane and propane. Since the fuel contains some butane, it performs poorly at cold temperatures. I think the OP is referring to propane appliances such as those made by Coleman or the cheap knockoffs that you can get at Wal Mart.
saddlesore has correctly recommended white gas fuel for cold temps and I agree.