Blue

What a wonderful array of symptoms and opinions...if it's the "running over Botts dots/washboard feeling" then the can of additive will probably do the trick. Millions of hi-mileage cars are able to benefit from this simple solution. I know we all get a little off on the idea of exotic exclusivity, but the solutions and solvents that go into an automatic transmission are all pretty similar, Varnish loads up on the internal elements.
The old fluid masked the symptom, the new fluid exposed it. "Mechanic in a can" isn't the only product designed for these high mileage transmissions. Wynns makes a product or two also.
If changing the wheels out fixed your problem, then what my 3 cars and my step brothers old truck experienced ain't the same, if that didn't resolve your issues, and you believe that your dealership did a complete and thorough flush/change, go to O'Reilly, AutoZone or Pep Boys and read some labels. Don't be too concerned that one of the symptoms these thing help cure is leaking seals as well. They won't harm good seals, it's just that many manufacturer's transmissions leak a little bit too by this point in their lives. Good Luck.