Maybe, your engine is running too lean. (that would explain the gas mileage improvement)
It could be a dead oxygen sensor.

All spark plugs gapped correctly?
-look at the sticker on the inside of the hood (it might read 1mm +0 -0.1; meaning max gap = 1mm, min gap = 0.9mm; divide by 25.4 to get the decimal inches you need for a wire feeler gauge)
-note: most spark plugs are sold pre-gapped to what the manufacture claims to be factory specified gap. But, that's not always the case.
When you check the gap, also check spark plugs for excessively high temp in cylinders. (most repair manuals have pictures of different spark plug conditions; running too lean would cause that.)

take care,
ChrisS