Cold has nothing to do with it. Lithium batteries are simply "crap" in this respect. They're the best we have right now in wide availability for size/capacity, but they're extremely fragile.

The bottom line is that you have to keep them charged at all times if you want them to last.

As Mark said, if they ever reach low voltage they're done. Even once below their magic number is enough to irreparably damage them. That's why everything that uses lithium cells has protection built in to prevent discharging below a certain level. The issue is that if you run them down in such a device, you had better charge them up again quickly, because they'll simply discharge on their own while not being used.

This is how we killed a few Sony "InfoLithium" batteries at my previous job. We just didn't use the video camera enough and even a new battery sitting around for the better part of the year without being on a charger would be near dead the next time it was used.

Batteries are expensive. Proprietary packages of them even more so. You might be able to find someone else out there selling rebuilt pack, replacements or parts to rebuild them yourself.

Wow. $1800.