Have a 97 sable,70k miles,check engine light on, all four codes,p0135, p0141, po155, po161,heated o2 sensors, performed tsb reprograming pcm, lasted about 1500 miles, codes came back on, no driveablity issues, cleared codes, came back on after second engine cycle, it would be extremely unusual to have all four o2 sensors to go bad at the same on, possible PCM??????

 

Check your fuses/relays (The power distribution box located in the engine compartment near the battery), wiring to the O2 sensors- you can try tracing wiring, wiggling harnesses, and voltage/resistance measurements for faults, if you have power to the sensors it sounds like the PCM/Computer is not energizing the heater circuits , therefore you are simultaneously getting these code readouts. The PCM's have been known for various problems internally(cold solder joints, parts). I would look around for a used one.