The fact that the water breathing spell doesn't come with penalties of any sort (you just breathe water like it was air, that's all) is a factor against the idea that lungs just become magically able to extract oxygen from water.
This is because a mammal breathing a liquid looks like this:
http://www.youtube.com/watch?v=ACQr0IZIb5I
(the link states it's water, but there's likely a fluorocarbon compound involved there).
You can see the poor rodent is quite busy trying to breathe, so doing anything else becomes quite difficult.
On the spot Andrew's idea would be the first and easiest to mind, and I second it - the players develop some form of gills which are removed when the spell ends. This means that they can try to hold their breath and reach the surface when the spell ends.
Also, since we're speaking about magic, there are millions of possibilities (they can absorb oxygen from water through their skin, the CO2 in their lungs is magically converted into O2...), all of which offer landscapes on alternatives uses for this spell. Only a few of these interpretations imply that the lungs are filled with water, and they do need a "magic-over-magic" explanation on why characters do not struggle to breathe a liquid in their lungs.
EDIT (yes it was a bit confused): So to make it clear, I would handle it by ruling that the characters' lungs do not fill with water during the duration of the spell, and at the time the spell ends, the characters will start holding their breath, with their lungs full of air. If you want to restrict the use of this spell solely to breathing water, then in my opinion magical gills (as Andrew suggested) are the perfect way to go. If you want to let the players be creative (and the spellcaster more useful), then you can rule otherwise - would you like the spell to be used to enter poisoned water, or a lake of blood, for instance?