Stonehenge and its Environs 134
Image by RiotGibbon

Yes, using ice or snow may have been part of the answer if the stones were moved in winter although only on downhill sections.

How cold were the winters 4000 years ago?

I believe when the Romans arrived 2000 years ago the climate was warmer than it is now, although I might be wrong on that.

I believe when the Romans arrived 2000 years ago the climate was warmer than it is now...
As warm, if not warmer (there were Roman vineyards in the south for example).

Something else that's maybe worth considering... today we have the notion of schedules, getting things done in one go and on time (well sort of :-), but perhaps when the big stones were moved people were more in tune with the right conditions. Maybe one year, or one season, was good and things were moved so far until conditions were good again. Maybe the stones sat midway for a season, or a year or two, before conditions were optimum again for moving them.