this is simply a matter of definition - (the graphics are extracted from http://www.fed.cuhk.edu.hk/~johnson/teaching/biology_lesson/molec ules/semnet/).
The definition of a solid is
,the definition of a liquid is
,and (to make it complete) the definition of a gas is
.You see that as soon as you have freely movable molecules, you have the liquid state. Of course it's not that simple if you think further - you can't always say "That's a liquid!" and so on, sometimes you have properties of one state compined with properties of another state.
But in order to define the state of a substance you have to exclude interfaces. In your case you have a lot of those ice/gas (or air) interfaces, and you can't apply the concept of solid/liquid/gaseous state - you can apply it for the ice clusters in this case, an there it is a solid. You need a ->homogeneous<- phase to apply the concept (i.e. physical properties are the same everywhere), otherwise you could ask "What's the state of matter of the earth?" - but you can't, because it's not homogeneous :) !
Bye,
Andreas