I looked again at the Astrobiology paper "Spiders: Water-Driven Erosive Structures in the Southern Hemisphere of Mars" and found the temperatures as far south as 81 S latitude where the spiders are found can reach 268 K, only 5 degrees C below freezing.
Also, this report from experiments showed liquid water carved channels could occur under current Mars conditions:

Martian Outflow Channel Formation by Water Erosion Under
Nonequilibrium Conditions.
Abstracts of the Lunar and Planetary Science Conference, volume 20,
page 666, (1989).
"An experimental study was carried out in a 2.4m by 4.9m cylindrical
vacuum chamber in order to investigate the possibility that martian
outflow channels were formed by the melting of ground ice. Frozen
soils that were subjected to an increased geothermal gradient at
temperatures about 273K and at an average pressure of 8.38 mbar,
melted and formed water-filled depressions and outflow channels. The
depressions formed as a subsurface ice layer thawed. Water initially
appeared at the surface either during gradual collapse of the surface
material or as geysers. The mode of appearance of water at the surface
was a function primarily of the strength of the ice and the
temperature of the water vapor."
http://adsabs.harvard.edu/cgi-bin/bib_query?1989LPI....20..666M
[full text]

In regards to the south polar "spiders" and the deposited fans, what is interesting is that the experiments showed geysers could result as well from water ice turning to liquid and gas under an ice cover. Whether the result of the subsurface melting was channels or geysers depended on the strength of the ice and the temperature of the water vapor.
In the case of channel formation, the report's description of how they formed suggests this could be similar to how the south polar "spiders" form:

"Water usually appeared as a moist area which gradually expanded. Small holes formed and gradually coalesced until one large water-filled depression existed. Water eventually spilled over the side of the depression and flowed downslope, carving a channel into the pure ice layer.
"Comparisons of the morphologic characteristics of the experimental channels to Martian outflow channels show many similarities. Like the Martian channels, the experimental channels were broader and deeper near the source, becoming shallower downstream. No obvious deposition of eroded material was observed."

If the spiders are on a level surface, then water overflowing the sides at several different places could carve several channels that would appear as the spiders "legs".
The NASA news release arguing for a pure gas release origin for the spiders and fans:

Spring at the South Pole of Mars.
AGU Press Conference
C. J. Hansen, A. McEwen and the HiRISE Team.
December 2007
http://hirise.lpl.arizona.edu/pdf/agu_press_conf_dec07.pdf

discusses unusual "lace" and "lizard-skin" textures on the surface on p. 8. These surface textures may look unusual because of an aspect of orbital imaging where positive and negative relief get reversed. By rotating the image you can make channels and craters that at first looked like raised features properly look like depressions. If you do this here, the unusual surface textures look quite like more familiar polygonal terrain and mud crack terrain, both of which require liquid water to form.

Bob Clark