When did Earth's oxygen atmosphere appear?

In my book Death from the Skies!, I described Earth's first mass extinction event: the evolution of bacteria that were able to ingest the primitive atmosphere of the time, and excrete oxygen. To these little beasties, oxygen was a lethal poison, and when enough accumulated in the atmosphere, it killed off a lot of our planet's nascent life. They couldn't survive their own waste (and, as I point out in the book, take home whatever cautionary tale from that you like). The survivors were ones who could use this new molecule to their advantage. Billions of years later, those survivors became us. But how many billions of years? Current thinking is that this event happened about 2.7 billion years ago. But new data seem to indicate that this event may have happened earlier than that. A lot earlier: like 3.5 billion years ago. This new data comes in the form ...