Are the tyres all the same size, in terms of wear. If not, then you have a different rolling radius - you're right ebola, it's really smooth off the tongue! - front and rear.
If you have replaced only one pair, try swapping them to the other end of the car.
One other possibility is a localised wear pattern on the TPS which may send a variable voltage signal back to the ECU.