The evidence is that came well before the 'Cambian explosion'. Sequence analysis of globins and respiratory proteins indicate that there was lots of oxygen around even before the evolution of the Eukaryotes. That's at least 1 billion years and more likely 2 billion years ago.
My own opinion is that the trigger for evolution of higher life forms was likely biological rather than environmental. I liked the hypothesis that it had to do with the evolution of eyes, which facilitated predation and led to an 'arms race'. I think this is an answerable question; I think that by delving through genomes we'll figure it out, even without fossil evidence; but at the moment the data are not there to answer the question.