Why do carbonated drinks effervesce vigorously when poured onto ice?

Why do they effervesce when you pour sugar into them?  Or a mentos?  Or those rocks that pop in your mouth?  

Because you just added more surface area on which bubbles can form (technically called nucleation sites).

Here's a fun experiment using a similar principle.  (DO NOT DO THIS!!!)  Take a very smooth container, fill it with one cup of filtered, warm water (the more pure, the better).  Microwave this in a 1250W microwave for 1.5 minutes.  (time and wattage are directly proportional here).  Open your microwave door.  Insert an object into the water.  Observe the water explode into your face.  Now call 911 to be transported to the nearest burn center.

What you just saw was the same thing: the water was super-heated (above boiling point) because there were no nucleation sites; everything was so smooth, and there were no impurities; consequently, there was nowhere bubbles could form.  Once you disturbed the water, the bubbles all started forming!

Moral of the story - if you must microwave water, dump a toothpick into it, and/or and make sure not to use a perfectly smooth container so that it doesn't end up exploding in your face

You were on the right track with Le Chatelier's principle; but we don't quite have an equilibrium to begin with when you look at an open can of coke.  The ice is simply acting as a catalyst.

Also note that when a fluid gets warmer, it will dissolve more solids.  But when it gets colder, it will dissolve more gasses!  (Otherwise, it would fizz less when it got colder from the ice).  Why else would a hot pipe freeze faster than a cold pipe?  (cold pipe has more air dissolved, and if you dissolve impurities you lower the freezing temperature).

Carbonated drinks contain carbonic acid dissolved in the solution.  Normally, the acid comes out of solutions by releasing carbon dioxide slowly.  This creates the bubbles and fizz of cola.  This continues until the soda is flat -no more acid in solution-.  The amount of time this process takes is dependent on the temperature of the solution.  This is precisely La Chatelier's Law.  The soluble Carbonic Acid is released to reach a modified equilibrium.

Gases are less soluble in cold liquids than warm ones.

Cool the liquid and - all other things being equal - gas must come out of solution.

Nucleation sites, as explained eruditely by another contributor.

Someone else said that gases are less soluble in cold water than in warm water - not true - gases are generally MORE soluble in a cooler solvent.