My best guess is you have an exhaust leak, maybe at the Vbands. If the exhaust isn't airtight from the head to the oxygen sensor, fresh air can get in and make the car read lean (possibly VERY lean). This is worse the closer the oxygen sensor is to the head, because those are used for trimming fuel. The last set of oxygen sensors after the cats are typically just to make sure the cats are working, but can affect amount of fuel dumped as the car could think your cats are cooking to death. So, I'd tend to think it's the first set of sensors which are critical.
It's super easy to swap the first set of oxygen sensors at the top of the downpipe. They're right next to each other.
See here:
http://2.bp.blogspot.com/_KkwAilVjAW...54engine11.jpg
The set of oxygen sensors at the top of the DP practically touch with factory downpipes. How sure is sure when you say you didn't swap them?