How long has this been going on? 1 tank? 2 tanks?
How are you measuring highway mileage vs city mileage? Just guessing? Reseting your trip meter repeatedly?
It sounds like the O2 sensor went bad, which will make the car run rich and negatively impact MPG. Sounds like you fixed it and your overall gas mileage is likely back to normal.