From
http://en.wikipedia.org/wiki/Water_(molecule)#Heat_capacity_and_heats_of_vaporization_and_fusion":
"Water has the second highest specific heat capacity of any known chemical compound"
This means it takes more heat energy from your body to raise the temperature of water to equal your body temperature, compared to air. Also water's thermal conductivity is higher than air's (0.6 vs 0.025 W/(m·K)), which means heat moves easier to water. In simpler terms water can absorb more heat from you, and do it faster than air, thus leaving you with less heat, and feeling colder.
Edit: Two more factors just popped into my head. First at these temperatures water is liquid and air is a gas. Therefore, water will be more dense than air, meaning there will simply be more of it close to you. Secondly air will be fairly static, whereas water will be pulled by gravity and only in contact for a few seconds before going down the drain (along with the heat you gave it), and being replaced with new water not yet warmed by you.
So we have a combination of water having a higher heat capacity, higher thermal conductivity, higher density, and being constantly moving. There is more of the water, which absorbs heat faster, and absorbs more before reaching equilibrium, and it is constantly being replaced by fresh unwarmed water. It's a wonder we don't get hypothermia in the shower.