In addition to having more heat capacity than dry air, humid air will deposit water molecules on the surface of the ice cream in the form of condensation. Upon contact with the cold ice cream, the condensing moisture releases latent energy, the energy of vaporization that originally was required to create humidity from water.
Each water molecule that condenses on to the surface of the ice cream releases enough latent energy to melt 7 water crystal molecules. The reason is that while it takes 540 calories per gram to convert water to vapor, it takes only 80 calories per gram to convert ice to water. So not only does water-laden air surround the ice cream with more heat, it's condensation releases latent energy which converts crystalline water to liquid water seven times more rapidly than would be the case in dry air.
Another reason for quicker melting in humid air is that water evaporates more slowly than in dry air, so a thin layer of water covers the ice cream, and this helps convey heat from the humid air into the ice cream.