Ok. I've heard this rumor at least 100 times. I can't find any information to substantiate it or any serious research done it. Is it a total rumor, or is there truth to it? Has there ever seen a study on this?
There was a related study that tested cycles at different temperatures.
One finding was that the cells in the cold cycle tests (0°C) lost capacity, but when they were brought back to 20°C the capacity recovered. The report points out that when the cells were maintained at a low state-of-charge, the capacity loss was less severe but those cells did not recover capacity when brought to 20°C.
I don't know at what temperature Li-ion cells will freeze, but if you were thinking about icebox temps, yes it has an effect. They will not lose as much capacity as they would at room temperature or elevated temperatures, but some will be lost.