How Cold?

I don't really think there is such a thing as "too cold". You just have to beef up your packaging accordingly with heat packs, etc.
I've shipped from here when it's been -20°F or less with no troubles. I don't receive any plants in the winter (by choice) because I don't want to ask the sender to take all of the necessary measures to be sure they're safe.

It is safe to say that cold preserves while heat kills, that is true. But the point of too cold is probably if they stay frozen for a long period of time.

I ship plants all year round with few problems. Keep you box big with plenty of newspaper, add heat or coldpacks when necessary and, most important, tell the recipient it is on the way so they can look out for it.