[chris (OP)]

Colder air conducts sounds more slowly than warm air. Intuitively one might think that it would be the other way around, since colder air is denser air, and denser media, like water, or metal, conduct sounds far more rapidly than air...?

[RD]

The denser the gas the more molecular collisions will occur per unit length.
Collisions of gas molecules will result in spinning the molecules to some degree rather than exclusively passing-on rectilinear motion.
So the more collisions the more energy is "wasted" on spinning molecules rather than transmitting the sound energy rectilinearly : the straight-line speed is reduced as a consequence of any rotation, (conservation of momentum).
So the denser the gas the slower the speed of sound because of the greater number of collisions per unit length and consequently the more energy wasted in spinning molecules   [ I think [?] ].

[evan_au]

As I understand it, the average energy of gas particles is proportional to temperature (temperatures measured in degrees absolute).

The kinetic energy* of one gas molecule is E=¹/₂mv²

This means that the average velocity of the gas molecule v is proportional to the square root of the temperature.

Sound generally travels at about 70% of the mean molecular speed in gases

Thus the speed of sound in air is roughly proportional to the square root of temperature (see green curve); the lower the temperature, the slower the speed of sound.

*The total thermal energy of diatomic gases like O₂ and N₂ is slightly more than the kinetic energy of the molecules, as various rotational and vibrational modes also share the energy. But these extra modes don't contribute to linear propagation of sound waves.

More details at: http://en.wikipedia.org/wiki/Speed_of_sound#Practical_application_to_air

[alancalverd]

The speed of a compression wave c=sqrt(K/d) where K is the elastic modulus of the medium and d is its density. The initial observation that water and metals are 3 - 10,000 times denser than air is obviously correct but their elastic modulus ("stiffness") is even greater, so sqrt(K/d) is 5  - 10 times that for air.

Cold air has similar compressibility to warm air but a greater density, so c decreases with temperature at constant pressure.