well like tony said tire pressure and sticky brakes could be a possibility. You changed the plugs, fuel filter so those are out.
Got a lot of junk in the trunk? Hows the air filter lookin? Do you drive the car hard? Could be bad gas.
In my experience after I have done a tune up i get some low mileage for the first tank or so, but nothing ever like 12 mpg.
