How can removing energy from a system do work? (ice) Water freezing into ice expands, damaging roads, breaking rocks, etc.
To my understanding, this is doing work (in a physics sense) by removing energy from the system.  How is this possible?
 A: There is no inconsistency. The first law of thermodynamics tells you that during any process the internal energy $U$ of any simple compressible system will satisfy $\Delta U = W + Q$ where here $W$ is the heat received by the system and $Q$ the heat received by it.
Upon changing from water to ice, the part of the system that undergoes the phase change does work on its surrounding since its volume slightly increases. The only thing it tells you though is that $\Delta U$ is even smaller than if you were to only take into account the heat extracted from the system.
So there is no contradiction at the first law level. Now, what you don't want is a contradiction at the second law level at fixed pressure and temperature during phase coexistence. And there is no worry on that side either because it's precisely the second law that enforces the phase change in the first place.
A: Classical case in gas: Put a tube upside down onto the surface of the water, cool the tube and the air got colder and suck the water up.
In your case, remember that when Ice turned into water, it cost energy. Thus you need to give heat or collision to the ice(input energy) to make the ice melt.
A: It does work because it operates like a Heat Engine where the energy travels from something with higher energy (water) to something with less energy (air) to create the work done by the ice. The air has to be colder than the water and below 0C in normal conditions for the water to even freeze.
It is just another Heat Engine-like working.
A: Consider the water liquid at its freezing point.
When water freezes its internal energy goes down - bonds are made.
The decrease in internal energy is equal to the heat removed from the water and the work done by the water in expanding against its surroundings.  
A: I guess the puzzle is to transfer heat out to surrounding and, at the same time, do work to the surrounding. This doesn't violate the first law for sure as the energy is conserved by decreasing internal energy. And this doesn't violate the second law of thermodynamics as well. 
A: The hydrogen bonds in water are like stretched out spring, and when water cools, the springs contract back snapping into ice (which is less dense than water). It's the potential energy stored in the hydrogen bonds doing the work to break the roads etc, as the system looses heat energy .
Heat energy causes the hydrogen bonds to separate and liquid to form (or the springs to stretch out)
