Water exposed to "air" (Co2, O2, Xenon and other trace noble gases) tends to break down into it's base elements quickly.
Well... no.
Don't confuse the O in H2O with the dissolved gases in water. Fish breathe by extracting dissolved oxygen gas from water... they don't break apart individual water molecues to get at the oxygen. <img src="/images/graemlins/smile.gif" alt="" />
The stale taste is mostly a result of the dissolved gases leaving the water. Which is why most water storage FAQs recommend aerating the water before drinking, usually by pouring it back and forth between two glasses several times.