Your transmission fluid "burned" after only 40K miles? That hardly seems likely, unless that trip from CA to VA was made in low gear towing a 5,000 lb. trailer! I suspect that your "quickie lube" guy smelled a quick profit and sold you a bill of goods. Normal auto transmission maintenance for Corollas calls for a simple drain-off of whatever ATF (auto transmission fluid) will come out, and replacing that same amount. This is done at least every 30,000 miles. However, waiting to 40,000 miles definitely would not have caused your fluid to be "burned" unless the car was seriously abused. The drain/replace cycle could have been started at that point, and repeated early after the next 10,000 miles just to get back on track.
Did you actually examine the fluid itself? How did it look and smell? Toyota ATF is bright red, and should look no worse than a deep red after it has some mileage on it. It should smell sort of sweet. If you actually saw and smelled it, report back what you saw/smelled.
Keep in mind that an automatic transmission "flush" is something that sounds good but isn't. The "flushing" action can stir up metal shavings and carbonized particles which can be re-distributed throughout your transmission and actually increase wear and tear, in spite of being mixed in with fresh ATF. The drain/refill procedure is ALL that is EVER necessary. Every 100,000 miles, you drop the pan on the transmission and clean out the bottom of the pan, and the magnets which are there to hold metal shavings. On some Corolla's, there is a non-replaceable filter which can be cleaned and returned to service. Then, you replace the gasket, pan, and refill the transmission and that's it.
Remember: NO FLUSHES. At all. Ever. Of ANYTHING.
Except your toilet!