Although water freezes at a fairly uniform temperature, lots of other things, even ones that contain lots of water, freeze at slightly to moderately different temperatures. It's likely that the potatoes that "froze" had a significant difference in starch content, or of some other "potato stuff" that makes a transition in state much like freezing of plain water at a slightly higher temperature.

Many materials other than plain water expand slightly during the transition from "squishy" to "hard," and the expansion of "juices" within the cells can break down the cells to produce a sort off "watery slurry" of "goop" that is very susceptible to rapid chemical degeneration resembling, if not exactly like, more typical "rotting."

Quite a few vegetables can suffer "freezer damage" at temperatures as high as 40 - 45 F (4 - 7 C). Typical refrigerator temperatures are usually at, or just below 40 F (4.44 C). Most prepared foods, and things like the milk, eggs, cabbage, and meat, are not harmed noticeably by temperatures down to around 35 F or even lower, but there are a number of things, especially some "leafy veggies" that can show what "looks like ice" at temps up to near 50 F in "still air."

I haven't heard of potatoes "freezing" at temperatures significantly above what's expected, but the variation in internal constituents could easily change their apparent freezing point by quite a few degrees.

Just as adding alcohol lowers the freezing point of water there are a number of other things that can be added to water to raise the freezing point. (Raspberry Jello?) I can't say what specific common "potato stuff" might cause what happened, but the event is not really a miracle so I wouldn't bother with a letter to the pope.

Chilling some vegetables can also cause a bit of "migration" of the juices, with "sweating" of the skins seen even with temperatures well above dew point, due to moisture coming from inside. Moisture, in the absence of air circulation can contribute to extremely rapid deterioration of some potatoe varieties.

Your local grocer might be able to tell you what "normal long-term storage" temperature is recommended for potatoes, but my recollection is it's usually something "near 50 F" with a minimum of about 45 F, although the potatoe variety and condition could swing that quite a bit either way.

John