Why does soda fizz when it meets ice?

This isn't the definitive answer that DumpsterDoofus was hoping for since I can't point to any scientific publications - they must exist but a quick Google failed to find anything from a reputable journal though there are loads of blog articles.

Anyhow, although in soda the carbon dioxide solution is supersaturated there is an energy barrier to creating a bubble. This is because the energy released by forming a bubbe scales with the bubble volume, but the interfacial energy required to create the gas-water interface scales as the bubble area so the total energy change looks something like:

$$ \Delta E = -Ar^3 + Br^2 $$

where $A$ and $B$ are constants and $r$ is the bubble radius. Typically the energy change will look something like this:

so creating a small bubble actually costs energy and creates a barrier that you have to get over for the biubble to grow.

The energy barrier can be reduced if there is a seed for the bubble to nucleate on. If you pour soda into a glass and look at where the streams of bubbles are coming from you'll probably the the bubbles come from a few spots on the inside of the glass. These are where defects on the glass surface enhance the nucleation rate.

Glass is actually a very smooth surface even on the atomic scale because the surface anneals as the glass cools, so it doesn't have a high density of defects to provide nucleation points. By contrast ice is not a smooth surface. It has many small cracks in the surface, and the thermal stress of adding ice to (relatively) hot water will crack it further. All these defects provide many sites for nucleation and enhance bubble formation considerably.

Lots of other materials will do the same. Allegedly cotton wool does (though I've never tried it), salt does, and most spectularly mints do (Google soda bomb for details!).

John Rennie's answer is pretty good. I will only add the reason for the energy curve is the different forces between adjacent molecules. And this mean different potential energies. H2O - H2O and CO2 - CO2 are more energetically favorable than H2O - CO2

CO2 - CO2 is found in the interior of a bubble. The energy drop is proportional to the number of molecules, or $r^3$.

H2O - CO2 is found at the surface of the bubble. The energy cost is proportional to $r^2$.

Dropping a third substance into the soda can help nucleation if 3rd - CO2 is more energetically favorable than H2O - CO2. Part of the expensive bubble surface is replaced by a cheaper surface. A smaller bubble gets over the energy barrier. The effect is enhanced if the bubble forms in a crevice.

I cannot explain why ice helps nucleation, unless the crystal structure of ice lowers the energy relative to liquid water.