Not really a spoiler, but in the movie Interstellar there was a planet that had frozen clouds. Is this actually possible? I know ice is less dense than water and so can float, but I'm having a hard time maintaining suspension of disbelief in this case as you would need a solid that was less dense than a gas AND was solid at the same temperature as the gas.
Yes, there are high-altitude clouds made of ice crystals, for example cirrus clouds. You do not need to fulfill any condition of having a lower density than surrounding air, much like regular clouds (composed of water droplets) do not require the density of water to be lower than that of air. The trick is that the individual droplets or crystals are so small that they do not fall at a significant speed (which can be 100 mph updrafts in the center of thunderstorm clouds, supporting huge hail-like balls of ice).
I think the answer is, in principle, yes, although in practice no.
First of all what you are not talking about, I think, is clouds of ice crystals: these are, as other answers have pointed out, common, but they are not what was depicted in the movie because they are not in any sense solid, they are just aerosols where the particles are ice. I'm also going to claim that the cloud doesn't need to be water-based: it just needs to be some kind of solid.
What you are after, in fact, is a cloud which is an aerogel. Aerogels are essentially made from gels by removing the liquid component, leaving a very low-density matrix. They are really odd materials. As far as I know you can't make aerogels from ice (the liquid component would have to be ethanol or something), although you might be able to: that's why this answer only works if the clouds don't need to be water-based.
Well, aerogels are denser than air, if only just, so they don't look like candidates. But I can get around this using a couple of tricks. First of all construct the thing so it has huge drag (I will leave the details to my aeronautical engineering minions -- my role here is merely to be the mad scientist who bosses people around): if it falls it will now fall only very slowly. Secondly heat it: it will now trap a lot of hot, low-density air. The resulting thing is essentially a solid hot-air balloon. It will rise, and then when it cools it will fall extremely slowly. It may in fact be kept aloft by thermal air currents or by heating from the Sun (it may be necessary to paint it black, sadly). It may need to be hollow, to exploit surface-to-volume gains as it becomes larger (a completely solid cloud of dimension $r$ has mass which goes like $r^3$, a hollow one has mass which goes a bit more than $r^2$ in the usual way). If it is large enough it will be able to support the evil genius lair which I will construct on top of it, of course.
I think, therefore, that this is possible in theory. In practice there are some problems: would it be strong enough to maintain integrity? would it be possible to construct a cubic mile of aerogel? could it arise naturally? The answers to all these questions are probably no. But I hope they are yes, because I want one.
As noted above, yes, ice crystals are present in high-altitude clouds such as cirrus and cirrocumulus, but importantly, these clouds are by no means solid, like the ones in the movie. Real ice clouds are incredibly diffuse and composed of tiny free-floating particles - therefore they would present no more of a physical obstacle than a regular cloud.