You said the 02 sensor is new... Is it factory Toyota or aftermarket? I ran into a problem on an 85 Toyota 22re w/ a bad sensor, so I threw new one at it. Mileage was HORRIBLE after. Turns out the aftermarket sensor was 1/2" shorter than the factory sensor and didn't even get into the exhuast stream.. So the computer was all confused and dumping tons of fuel in to compensate.

Worth a check if it's aftermarket... if it's factory Toy... then I don't know what to tell ya.

Brian K. Gallus
I have nothing important to say.