Yes, O2 sensors do go bad. And the o2 sensors being more than likely killed the cats.
An automotive oxygen sensor, also known as an O2 sensor, lambda probe, lambda sensor, lambda sond or EGO (exhaust gas oxygen) sensor, is a small sensor inserted into the exhaust system of a petrol engine to measure the concentration of oxygen remaining in the exhaust gas to allow an electronic control unit (ECU) to control the efficiency of the combustion process in the engine. In most modern automobiles, these sensors are attached to the engine's exhaust manifold to determine whether the mixture of air and gasoline going into the engine is rich (too much fuel) or lean (too little fuel).
This information is sent to the engine management ECU computer, which adjusts the mixture to give the engine the best possible fuel economy and lowest possible exhaust emissions. Failure of these sensors, either through normal aging or the use of leaded fuels, can lead to damage of an automobile's catalytic converter and expensive repairs.
The downside of oxygen sensors is that they defeat many fuel saving technologies. If the engine burns too lean from any modifications, the sensor detects that the exhaust is too lean. It then sends the signal to cause the injectors to enrich the mixture by supplying more fuel. This causes the air-fuel mixture to stay within the stoichiometric ratio of 14.7:1 on a typical domestic vehicle.
There are ways to overcome this efficiency defeating mechanism. Several companies manufacture a device that can be inserted inline with the sensor and tricks the voltage signals into thinking it is within normal parameters. Therefore, any modification for cleaner burning will not be defeated by the oxygen sensor.
This self-defeating mechanism is why some legitimate fuel saving technologies actually cause a loss in gas mileage
Gotta love wikipedia...