I would pull the pan. Sounds like something is goofed with the linkage, be it the pin in the manual control valve, or the spring thing with the roller on it that gives the trans positive shift detents. You did check that the park pawl operates smoothly before you put the tailshaft housing back on right?
IMHO it doesnt sound like a cable adjustment thing because theoretically, nothing should have changed when you rebuilt the trans, provided you didnt take the NSBU off.
ben