Just got another code:
P1155: Air/Fuel Sensor Heater Circuit. (Bank 2 Sensor 1).
I guess Oxygen Sensors are a wear item, and I just passed 90k miles, so I should expect it.
I already replaced the hard one near the firewall, when I got a P1135. This is the same sensor, only on the other side (bank).
Just sent an email to 1st Toyota Parts - to get the part number. If my guess is right, looks to be about $148.