Great news. I explained the issue in detail to the transmission rebuilder and he said right away that it sounds like the K1 (IIRC) accumulator was faulty in the new valve body, that something must have gotten messed up during the rebuild. He said that he would immediately build and send out a new valve body to my mechanic, under warranty, free of charge.
A few days later, the new valve body arrived at my indy, and a week later it was in the car. I got it back today and drove it all over town giving it a thorough shakedown, and I am happy to report that the issue is completely resolved. Not only are all the downshifts perfect, but the upshifts are even a little better too. I can truly say that the transmission functions perfectly now. Hooray!
So it was indeed a faulty rebuilt valve body. Icing on the cake is that the rebuilder was absolutely responsive, cooperative, and couldn't've treated me better.
Thanks everyone for the help. It's good to have my beloved E320 back better than ever!
