I know this will sound crazy, but a guy I met @ E-town had codes for the sensors like yours and when he installed the headers, removal of the ox sensor was easy, but he didn't reinstall them with the special GM anti-seize and he would get code problems. He replaced the ox sensors and the factory replacements come with the anti-seize already applied and his codes cleared with no more problems. This is the only time I have heard of this, but you can bet when I had mine installed I took a can of the anti-seize to my installer and he laughed because he already had the product.