When dispensing liquid nitrogen, why does the surface get wet rather than frozen?
Your "first thought" is basically right, with one clarification. The addition of "so much new water" to the existing ice results in the formation of liquid water due to the latent heat released upon condensation. This results in melting of the existing frost and thus the transitory existence of liquid water.  

Also you can rule out oxygen condensation.  Firstly there is some insulation between the 77 K liquid nitrogen and the atmosphere, so the surface is not likely to cool all the way to the 90 K boiling point of oxygen.  More importantly, oxygen would not condense from the air at 77 K anyway.  You have to think in terms of saturation vapor pressures, and the vapor pressure of oxygen in our air is only about 0.21 atmospheres.  

By analogy, albeit an extreme one, the temperature in the coldest regions of our atmosphere drops below the sublimation point of carbon dioxide.  Does that cause the formation of dry-ice clouds?  Not even close. The sublimation point of carbon dioxide in this example, like the boiling point of oxygen in your example, is only relevant at 1 atmosphere of pressure of that compound, and in neither case does our atmosphere contain 1 atmosphere of either of those compounds.