Googling around, you can find anything from "LiIon rules the cold" to "LiIon is useless in the cold". So you have to choose who to believe. I generally find batteryuniversity.com to be reliable.

http://www.batteryuniversity.com/partone-15.htm
"-20°C (-4°F) is threshold at which the nickel-metal-hydride, sealed lead-acid and lithium-ion battery cease to function, the nickel-cadmium can go down to -40°C (-40°F)"

but later on
"Lithium-ion may be used down to -30°C (-22°F) with acceptable results. Larger packs will be necessary to compensate for the reduced capacity at these temperatures. "

So apparently that's a usage of the phrase "cease to function" that I was unaware of.

There are also apparently different breeds of LiIon, some manganese based and some cobalt based, and possibly others, and they behave differently.

If my NiMH pack ever dies, I'll probably try a LiIon pack to see how it does.