You have a restriction in the air intake, or a faulty sensor on the front side of the engine (ECT, Ambient, IAT, etc.) or a vacuum/air leak. It's most likely actually causing a lean condition and the old stuff as well as the new stuff was/is reading right.