I know that alot of newer transmissions have carbon fiber materials in them, some of the CVT's out there have notes about this in the manuel, and will turn the the fluid black within a couple thousand miles.
You might want to call the shop and ask them.
However, if it is just a rebuilt 99 transmission, I would drive it around town, make sure you get up to highway speeds to get through all the gears.
1000 miles or so, then go get it serviced.
It might be interesting to put 6oz of Auto RX in there before the servicing to get all the residual break in stuff out.
BTW, I have about 30,000 miles on my '02 taurus since the transmission was last serviced, and the fluid is still pretty red.