Then it probably was just a faulty O2 sensor. Not very common when you buy good parts!

I was just commenting that your symptoms are very much like a fouled O2 sensor from certain chemicals.