I must be doing something wrong because I've definetly had garage propane heaters not work well in cold temps. They start off strong but then they run out of pressure even with half a tank of propane left.
This certainly isn't the answer for all weather conditions but I have a toque and heavy pair of socks packed in each of my sleeping bags. They're always there just in case.