Oh, duh! I was thought you were talking about it not automatically downshifting, not being unable to move the shifter. Kinda the same way you need to hit the brake to shift out of park, right? That sounds like the shift interlock cable needs to be adjusted.
You can pry up the trim around the shifter and you should see two cables. I believe the one on the passenger/right side is the interlock and the other is the cable to the tranny. There is an adjuster on the cable towards the front tha may need adjusted. The piece that moves up to lock it into park may have a groove worn into it which needs filed out. Just have to pull the cover and see how it woks and whats hanging up.