The only problem with your transmission is the internal seals are leaking causing poor pressure for gear changing.
As this BMW bulletion reads:
2. After the vehicle is parked for an extended time (for example overnight) and a delay of 2 to 3 seconds is experienced from the time gear selection is made until gear engagement occurs. If transmission serial number is less than 4834735 install latest seal kit P/N 24 27 1 423 311
To install this seal kit the trans must be removed, disassembled and seals replaced. Something for a dealer to do. My e34 has had this same problem, but only when going into reverse. I bought the entire seal kit, then the problem went away and hasent comeback yet.
Try dealing with it for a week of two, if it doesnt go away your looking at paying about a grand for the fix. And as for that rebuild that was done to the trans, are you sure it was a complete rebuild or not just a new torque converter because BMW doesnt rebuild trans's, they only replace them. You might get a rebuild at a trans shop but no dealer.