[Gazza]

During the early stages of evolution, the earth's atmosphere was made up of reducing gasses, such as dihydrogen, methane and carbon monoxide. Anaerobic organisms used enzyme catalysts based on Ni and Co to synthesise simple molecules from these gasses.
However, since the advent of dioxygen, aerobic organisms prefer to use enzymes based on metals like Fe, Cu and Mn. Why is this?

[Arkcon]

During the early stages of evolution, the earth's atmosphere was made up of reducing gasses, such as dihydrogen, methane and carbon monoxide. Anaerobic organisms used enzyme catalysts based on Ni and Co to synthesise simple molecules from these gasses.
However, since the advent of dioxygen, aerobic organisms prefer to use enzymes based on metals like Fe, Cu and Mn. Why is this?

I was not aware that it was as cut and dried as this question seems to state.  Does you have a source for the second statement in the question?  FWIW, Ni and Co are still found in co-enzymes nowadays.

[deadally]

I can stab at this in the case of Cu and Fe.  Copper often plays a role in forming structures of enzymes that interact with oxygen (Superoxide dismutase comes to mind).  Without Cu, these structures do not form properly to let in other metals that catalyze the oxygen stuff.

In the case of Fe, its many oxidation states help the heme substructure maintain a load of different funcitonalities and power levels.  I believe the Fe itself likes to bind oxygen, which makes it very useful in oxygen delivery!

The enzymes kind of form around it to help facilitate the needs of the organism

[azmanam]

Interestingly, your question presupposes enzymes - not simple molecules by any means.  Rather, enzymes are made up of simple molecules (amino acids).  An interesting spin on the question asks how did these sometimes highly oxidized amino acids form in this reducing environment in order to be able to assemble into enzymes capable of making 'simple molecules?'