Did you flush or replace the cooler?
Here's why I'm asking. Oil flows from the torque converter into the cooler. The ability to flow normally is what causes a high pressure drop across the clutch inside the torque converter. I didn't learn this until relatively recently, but there is no rubber seal for the lockup clutch. It relies on pressure drop across the clutch plate to achieve the clamping force. So there is always a small amount of leakage past the spines and the friction material. Unless of course, there is a crack in the plate, which does happen.
Anyway, If the cooler (low pressure side of the clutch) is partially blocked, then there may not be enough flow...until the oil warms up. Once the viscosity drops, flow through the cooler increases and you have a big enough pressure drop across the clutch to hold lockup. I'm probably grasping at straws here, but it's not easy to imagine a situation where higher temperature and lower viscosity would cause things to start working like this.
That being said, the fact that you didn't rebuild the transmission after the overdrive replacement means there could still be some shrapnel left that's playing havoc with the valve body. I'm not giving you crap for this, since you managed to get many thousands more miles out of the transmission even if this is the case (and we don't know that it is...).
If the solenoid body doesn't fix it (relatively easy to replace), and you've already addressed the cooler, I would almost suggest getting a different torque converter. Also inspect the pump valves while you have it apart, since the lockup valve is located there.