OK. I can look this up, but this is easier. When you open a soda it fizzes. When you put the soda in the freezer and take it out BEFORE it freezes, then open it right away if fizzes like CRAZY and FREEZES (not completely, but a lot).
How come?
Try dropping a teaspoon of sugar in a glass of soda and see what happens. 
I think your original question goes to colligative properties, at least in part and on properties of gas solubility in liquids which is dependent on temperature and pressure. Oxygen is more soluble in colder water than warm water. Offhand, I would guess the same to be true for CO2. But this seems to be the opposite of your observation.
Maybe it is a case of supersaturation at the lower temperature, which is a semi-stable state. Releasing the pressure could destabilize the equilibrium releasing excess CO2. Freezing point of liquids are depressed by increasing concentrations of solutes, e.g. salts (CO2 in this case). This is called Freezing point depression, and can be used for measuring the concentration of solutes or the purity of liquids. In essence, liquids with greater amounts of solutes can be remain liquid at temperatures farther below their freezing points. This isn’t a great range, usually afew degrees centigrade. In this particular case, if the CO2 is depressing the freezing point, once it begins to “fizz out” the freezing point of the soda rises and the soda can finally freeze (assumes that the CO2 fizzes faster than the soda warms up).
I’m still not exactly clear as to why the soda fizzes more, but I still lean towards disturbing a super saturated state. Chilling the soda allows more CO2 to leave the headspace and dissolve in the soda. The soda is in a semi-equilibrated state under pressure and below the freezing point. Releasing the pressure abruptly disturbs the semi-equilibrium, leaving the remaining soda below its freezing point.
Another possiblity relates to the sugar observation and the possibilty of ice crystals being present in the soda. But, I’ll leave that for another post.
Water expands when it freezes, so the gas inside is more pressurized (i.e., same mass, less volume)?
This makes sense. Freezing temperature depressed by the CO2. When the CO2 escapes, the liquid can freeze. I like it.
Someone else said PV=NRT. I’m sure that is technically related, but I like this explanation.
PV=nRT
The expanding CO2 (released when you open the can/bottle) cools pushing the liquid below the freezing point. This is the same reason CO2 cartridges get very cold when used.
"The expanding CO2 (released when you open the can/bottle) cools pushing the liquid below the freezing point. This is the same reason CO2 cartridges get very cold when used. "
While this (adiabatic cooling) is true in general, thermal mass balance of a little bit of gas (very little bit of mass) dissolved in a lot of fluid (large amount of mass) won’t produce significant temperature changes in the liquid in this case. Furthermore, how much pressure is the CO2 under in the first place? I think it is far less than a CO2 cartridge used for inflating tires for instance.
As far as the Ideal gas law is concerned, I think there is a problem because the observation is not for a closed system. In other words, when the soda is opened, the CO2 is vented into the atmosphere, so the volume of the new space that the gas occupies is larger. In a closed system, say the soda can in an enclosed box, opening the can would result in changing the initial volume V1 (airspace inside the can) to V2 (airspace inside can and box). (The volume the dissolved gas occupies in the soda can be ignored at this level of analysis.) From PV=nRT, one can derive P1V1=P2V2 (assuming constant temperature). For a simple thought experiment, the “box” could be a flexible balloon which expands until it reaches one atmosphere pressure. Then P1 can be calculated, P1 = (P2V2)/V1
For temperature changes, one can derive (P1V1)/T1 =(P2V2)/T2 or T2=(T1P2V2)/(P1V1). In the initial example, final pressure was one atmoshere, but the volume was uncontrolled, so V2 is not defined. Furthermore, this equation calculates the gas temperature, not the liquid, and more than likely T2 of the gas is much closer to room temperature in the uncontrolled situation (non-closed system).
The more I think about it, the less PV=nRT has to do with it.
Water expands when it freezes, so the gas inside is more pressurized (i.e., same mass, less volume)?
Water doesn’t expand, frozen water goes through a transition from one crrystal structure to another which has a different volume per molecule, just below the freezing temperature. Dissolved gas, like most solutes tend to occupy interstitial spaces, i.e. empty “spots” between the molecules of water. This isn’t true for solutes which are hydrated by water.
But, in any event, the original observaton was that the soda didn’t freeze until after it was opened, so therefore no increased pressure on the dissolved gas (if it does exist). Lower soda temperature will effect the solubility of the CO2 in the soda, though.