I've had this symptom, too, for maybe a year. I posted here a couple times and never got any suggestions.
My theory is that the cable which links the brake pedal to the shifter lever is somehow the culprit. On mine, the brake-shifter interlock no longer works, too, which makes me suspect this. In other words, I can shift out of park without stepping on the brake. What about you?