mostly myth
It has more to do with the charge than the concrete. A fully charged battery can handle temps well bellow freezing. As the charge drops, the freeze point comes up. A completely dead battery will freeze just below 32F. This will destroy the cells, and its a goner.
Adding to the problem...I have an attached garage. Its not heated, but picks up some heat from the house, sun on the roof etc . So air temp stays above freezing most of the time. The concrete near the wall (where a battery is likely to sit) is going to drop below freezing much sooner than anywhere else.
Batteries in storage anywhere will lose charge, they lose charge quicker if dirty because the dirt hold moisture and gives a path to ground. So, the dirty battery on the concrete in the corner of the garage loses charge and freezes quicker due to faster heat transfer through concrete and it all gets blamed on the concrete...