I ended up at a Mazda dealer today, again while working up in NH, and had the tranny flushed and filled, as well as the front and rear differentials drained and filled. I have nearly 85,000 miles on my '08 at this point and since I do mostly highway driving, I wasn't worried that I was waiting too long. After the service was complete, the tech showed me the old fluid and said it really didn't look that bad. So, I think I'm good for another 85K!!....but I'll likely have another vehicle before I get to that point.
It wasn't cheap, but this dealership was less expensive than most of the others I contacted....the entire bill was just under $350 and that included a $22 materials waste charge. They did charge me for 12 quarts of ATF fluid (I thought it only took 10) but I was surprised to see that they 'only' charged me $6/quart. So far so good....I drove about 120 miles home and it shifted as smooth as ever. I'll just keep my fingers crossed that the flushing didn't dislodge any foreign material.