Finally replaced all 4 O2 sensors w/ generics for $160.

[Rodger]

I would check to make sure all of your connections are tight and that no wires have been swapped anywhere. It's usually a really good idea to solder these connections, as the signal output from the sensor is barely 1 volt (at maximum) and any resistance at all will hide the true value. Eve if you're only soldering one wire per sensor, make it the black one.

If you have a multimeter, set it to DC volts. With the engine fully warmed up, disconnect the O2 sensor prior to the first cat (nearest the engine), put one lead on the black wire coming out of the sensor and the other lead to a clean ground on the engine or chassis. With the engine running, you should see voltage vary between around .2 to .8 fairly slowly at idle, maybe 2 or 3 cycles in 10 seconds. Now shut off the engine, but leave the key in the ON position (dash lights all on). Next, check the grey wire coming out of the car harness for continuity to ground (meter set to Ohms). It should have almost no resistance to ground (good continuity). Lastly, verify the two white wires have +12V (meter set to DC Volts) on the car side of the harness.

You didn't get any anti-seize compound on the heads of the sensors, did you? Based on the codes, it sounds as if wires are either swapped (hard to do, I know), loose, or the whole lot of sensors is bad. Were any of the wires faded or damaged in some way on the car harness?