Sorry for the long response in advance. Transmission fluid changes are a hotly debated subject so there's a lot of information out there. This is my attempt to try to boil it down so you can make an informed decision.
I've been researching something similar recently and here were the understandings I gathered. Based on what you said, though, (and the interval CharlieRB pointed out) the quick answer is yes, you should replace the fluid.
- The only time you may not want to change the fluid is if a rebuild is known and inevitable and you're trying to postpone that as much as you can. The reason is transmission fluid is an excellent solvent and will clean away things like varnish deposits and burnt clutch material which may be serving as the spit and bubble gum that's keeping it running right now. In this case you'll be getting new fluid with your new transmission ;-)
- If the fluid was very overdue or was dark and/or burnt but the transmission was still otherwise functional, replacing part of the fluid a number of time over thousands of miles would be advisable. Changing it all at once may knock buildups loose/clean things up too quickly which can cause the transmission to start malfunctioning. Introducing new fluid gradually (30-50% at a time, with something like 3k miles between changes) can minimize or sidestep these effects completely. I've seen this referred to as the new fluid "shocking" transmission components.
- If the fluid is in reasonably good condition (red/brown, not black, not burnt-smelling), then just get a flush done.
If you do get a flush, make sure they use a gentle flushing technique. Some flushing devices pressurize the new fluid going in which has a tendency to break up and dislodge buildups. Those bits are then free to float around and get stuck in other places where they will cause problems. The gentle devices basically pour in new fluid as the old fluid is evacuated. Any subsequent cleaning done by the fluid is gradual and results in smaller pieces which are unlikely to upset anything.
Also, do not go to a quick-lube shop for this. They have a long and sordid history of fumbling the simplest of tasks and not taking responsibility for it. A reputable repair shop will have better equipment and know-how.