check the simple things first.
Like checking to make sure the harness is on 100%
sometimes it's those little things that screw us
If all the simple things are good, I'd say it's that 02 sensor you put in. Maybe try taking it out and putting it back in

shrug: you never know). If that doesn't work, try a KAM reset.
Here's my theory (that may be completely wrong): Your car's adaptive strategy changed things up since you had an 02 sensor that was faulty or on its way out (it adapted to ur old O2's readings). You replaced it with a perfect condition O2 sensor...so that's working like it should, but your computer is still using the values it learned from the malfunctioning one. So maybe your computer learned that "voltage x = stoich"...but now, that same voltage causes the computer to +/- fuel. My guess is it just needs to relearn those values or do a KAM reset.
The only problem with my theory is....that O2s aren't used in open loop...like when you first start your car in the morning. If I'm not mistaken though, your computer uses CL information in its decision making process for OL...so my thoughts may still hold water
rambling I guess, hope I helped some