Orange sky 3.7 billion years ago because there was little oxygen? PhysOrg quotes Martin VanKranendonk of the University of New South Wales and director of the Australian Center for Astrobiology:

Because the atmosphere had very little oxygen and oxygen is what makes the sky blue, its predominant color would have been orange

Is this correct?
 A: Nope!  The blue sky comes from Rayleigh scattering through air, but pretty much any gas whose molecules are decently polarizable will work equally well - it doesn't have to be oxygen.  I suspect the guy probably said that there was very little atmosphere and atmosphere is what makes the sky blue (although does it really count as a "sky" if there's no atmosphere?...) and the reporter misunderstood.
A: Yes, it is correct in the sense that this is the commonly held idea about the color of the sky on the early Earth. This idea about the color is derived from the composition of the early atmosphere. The main component was methane. The color is not due directly to the methane but to some other hydrocarbons formed when the UV hits the methane molecules. These hidro-carbons produce a sort of orange haze.
This effect is stronger than that of the Rayleigh scattering on the gas molecules.
Titan has a methane rich atmosphere and this orange sky was observed by space probes, fact which supports the theory about Earth's atmosphere early color.  
When he mentions the oxygen, he probably means that oxygenation of the atmosphere removed the methane and the atmosphere became more transparent, the orange haze disappeared and the main effect to determine the color was Rayleigh scattering on small gas molecules. 
