Before my first oil change, my mileage had been getting worse and worse -- averaging 30 mpg! But I finally got it done at 6700 miles, using Mobil 1 Synthetic 5W-20. No improvement on the tank immediately afterwards, but after that, it was back up to ~34-35 mpg.

If it's actually worse after an oil change, maybe they used bad oil. There are petroleum 0W20 oils and they're bad -- you need synthetic for good performance.