The ingredients for snow are: (1) a temperature profile that allows snow to reach the surface, (2) saturated air, and (3) enough lifting of that saturated air to allow snow to develop aloft and fall to reach the surface. In a situation when it is said "it is too cold to snow" there is in reality not enough lifting of air that causes snow to reach the surface. The phrase "it is too cold to snow today" probably originated as a misapplication of the relationship between temperature and the maximum amount of water vapor that can be in the air. When temperature decreases, the maximum capacity of water vapor that can be in the air decreases. Therefore, the colder it gets the less water vapor there will be in the air. Even at very cold surface temperatures significant snowfall can occur because: (1) intense lifting can produce significant precipitation even at a very low temperature, (2) the temperature aloft can be much warmer than the temperature at the surface. The relatively warmer air aloft can have a larger moisture content than air in the PBL, (3) Moisture advection can continue to bring a renewed supply of moisture into a region where lifting is occurring, (4) Even at very cold temperatures the air always has a capacity to have some water vapor. If the air cools to truly frigid Arctic temperatures such as -40 C and below then the moisture capacity of the air will be so low that likely not much snow can occur. Only at these extremely low temperatures is the phrase "it is too cold to snow" fairly valid. Reference Link: http://www.theweatherprediction.com/habyhints/222/

Yes, it can.

I love the idea of the old wives tale of it being to cold to snow. I think it more comes from the fact that it's often colder when there's a clear sky (due to the heat not being kept in by the clouds) and it won't snow if there's no clouds

No. Snow at very low temperatures is rare, but not impossible. All that is required to produce snow is moisture in the air and some way to lift and cool the air. From a practical point of view, most of our snowfalls occur when the air temperature at ground level is between 15°F and 32°F. The "warmer" the air, the more water vapor it holds and the easier it is to produce a cooling effect through lifting actions such as updrafts.