Did the dealer ever do a loaded resistance check from the pin connection that plugs into the o2 sensor back to the ECM connector? Try doing some wiggle test while its under a load.

Second thought...leaking antifreeze. Were the 02 sensors ever white? Login to read more.