John, you don't need to re-balance the driveshaft just because you change u-joints....if the shaft was balanced beforehand, it will still be balanced afterwards. But on the other side of the coin, if it wasn't in balance before, it still won't be. So, if you are sure that it is balanced (no weights have been knocked off, it hasn't been rubbed on rocks, etc), I wouldn't re-balance it....
BTW, I believe it was Tucson Driveline that did the work for Kyle. Sorry, no contact info, but they are in the yellow pages.
Your description is typical of a driveline problem. If it was a steering component/alignment, it would be more pronounced in the steering wheel than in the rest of the vehicle. Front driveline vibrations will be more pronounced in the steering than rear driveline problems....something easy and free to check is to rotate your tires, and see if ANYTHING changes (where the vibration is felt, the intensity, when it starts/stops, etc).
It is a good idea to WRITE DOWN all the symptoms, and the conditions under which they happen. 2 or 3 weeks into troubleshooting it is easy to forget if vibration started at 35mph or 40 mph. Having a solid reference point helps. You may change one thing (suspension component, steering component, etc) which has a small effect on the vibration...but if you are not 100% sure of the original condition, you won't be 100% sure if the change is real, or if you just imagined it. This will help you alot as you chase down the problem. Of course you also want to write down what changes are made, and what effects they have had. Don't simply say "nothing changed", take a new piece of paper, drive the lexy, and write down all the symptoms. Then go compare it with the original. Otherwise it is easy for your mind to tell you nothing changed just because the conditions are similar. Even little changes help point you to the problem.....and more information is better.