We do. See http://en.wikipedia.org/wiki/Moons_of_Saturn
And BTW, there are plenty of examples of moons made of ice, and at the temperatures of the outer solar system ice can be harder than rock (and BTW, Neptune and Uranus are called "ice giants"--care to guess why?).