Ton's of good stuff in here already. Sooo I'll add to it.

Our transmissions are programmed to not lock the TCC until they are up to a certain temp. I forget what temp it is..I think it's something low like 100F.

When you are in third with the TCC locked up, it should release, shift to fourth and reapply the TCC. This is kind of what I hear you saying it's doing. Although since you are noticing it, maybe it's a little slower than it should be. On the HD trans (which you have) the factory programming on light throttle will shift into 4th right around 42mph. TCC can lock at that point, however it also might not. TCC lock/unlock is based on torque, load etc. Meaning if you are heading up a hill, your TCC can unlock to give allow the engine rpm to raise up and provide you with the power needed w/o downshifting.

A couple other things that factor into how your transmission shifts are the TPS, MAF and the ignition system. If you say had Platinum plugs in the engine, then they might cause you to have slight misfires or poor ignition and this could cause the pcm to be goofy with load calculations and shifting/tcc lockup.