Free Flow

The first stage of a regulator serves to reduce the air-supply pressure from the maximum tank pressure (often in excess of 200 bar) to around 8-10 bar more than ambient pressure.
When air is depressurised in this way, it becomes very cold. There can be a drop in temperature of many degrees in the immediate vicinity.
If the surrounding air or water is already very cold, ice can form; and this ice can cause the moving parts of a modern downstream regulator to freeze open. The result is a massive and exponential free-flow of air.
This free-flow usually manifests itself at the second stage, as this is the route of least resistance. If you could shut off the supply to the second stage alone, the problem would probably shift to the alternative second stage (octopus) or even a direct-feed inflator.
The surrounding water may seem very cold, but it will have a lot more heat in it than this air. Water is rarely colder than 0°C. It's important to warm up the air supply by surrounding it with the small amount of heat that is in the water.
There seems to be two different philosophies regarding regulator design. Some designers of regulators intended for use in cold water try to keep the water away from the moving parts, and this is where the dry-sealed environmental kit comes in.
Other designers try to maximise the flow of water around the moving parts, thus picking up whatever warmth is in the water. Many designs use metal parts in the second stage for the same reason. The metal acts as a heat-sink, keeping the moving parts above 0°C. Some regulators have additional metal added in the form of fins or heat-exchangers.
How else can you stop a regulator from icing? First, be sure that your air is dry, by having it supplied from a double-filtered source, as is done with nitrox.
The diver can avoid the circumstances that might lead to ice forming by avoiding:

heavy airflows while the regulator is in the cold air at the surface before diving.
exhaling moist air back into the second stage. Take those all-important check-out breaths while both stages of the regulator are submerged in the shallows, rather than on the shore.
jumping in and provoking a free-flow at the cusp between air and water at a time when the first stage is wet but surrounded by the freezing atmosphere. In this case icing is inevitable. This can happen with almost any regulator and the only answer is to turn off the air supply at the tank, submerge it in water, and wait for the ice to melt.

Ironically, it is the regulators that are able to supply the greatest amounts of air, those that breathe the easiest, that are most vulnerable to free-flow due to icing. In the days when most regulators were made of heavyweight metal and had all the breathing characteristics of an asthmatic pensioner running after a bus, icing was rarely a problem.
The trick is to immerse the whole regulator, including the first stage, gently, and to start breathing from it only once it is completely submerged.

Swithland Woods 29th April 2006 - Ric Catell had a free flow at around 30m Pics below show result. His first and second stage were still iced up over 45 mins after he exited the quarry!!

Thanks to Moxy for the pics off his camera phone.