I didn't honestly think it was electrical from what you first wrote, but here's a thought; did you install two o-rings when you put the new solenoid in, or just the outer one? Overdrive is allowed by blocking the fluid between the inner and outer ports. A leak between them would act like a de-energized solenoid and inhibit overdrive.

If you tried it with the kickdown cable disconnected, then that's not it either.

My own AW does something similar to the newer units that are designed to hold off OD until normal coolant temp is reached to speed the warmup. However, there is no thermostatic control in these units.

A fluid change may make you feel all warm and fuzzy but it's not likely to help the upshift problem. If it is, in fact, a problem in the valve body - new fluid isn't going to "flush" out anything. Nor will it rebuild worn slip rings to the overdrive brake. If the brake piston seals are hardened from years of poor maintanence, it may help soften them enough for better cold operation by next winter...but nothing in short order.