At what point does decreasing solvent temperature cause a decrease in gas solubility? Example: At constant pressure, carbon dioxide becomes less soluble in water as temperature increases. We also know that carbon dioxide becomes more soluble in water as temperature decreases.

Does introduction of order and loss of kinetic energy of solvent molecules eventually lead to a decrease in a solvent's ability to accommodate gas molecules? It is hard for me to believe that ice cubes can hold gas more effectively than the same volume of a glass of water.
Rules such as "solubility of A in B rises with lower temperature" are only meant to be used if there is no phase transition of the participating substances.