Re: mileage decrease / transmission ?
You doing actual mpg and not relying on computer, which tends to be off. Fill up, mark odometer miles and how many gallons (not as important first logging and subsequent), then drive how ever much then fill-up again; divide miles driven by gallons it took to fill up. For some odd reason, I've been logging every gas visit since like 1990, ha ha. Interesting to see the trend of gas prices!
Have you checked your air pressure lately? How about your air filter? PCV?
I know you're saying about the fluid and such and timing though. I would assume they used the right stuff and it's weird that it would be thicker when new, unless the old was just worn out. I am not familiar on how thorough their "flush" is, but it makes me nervous flushing oil passages (esp in the engine and imagine tranny is worse), as sometimes sludge will get dislodged just enough to go where it's not supposed to. Not sure if you've ever looked at a valve body, but there are all sorts of critical passages, springs and balls in there!
Well, not saying that is the case, but just thought I'd throw it out there.