Auto-trannys have an interlock system. It's not supposed to let you shift out of Park unless you're stepping on the brake. Check whether that mechanism at the shift lever is adjusted properly?

(If the switch on the brake pedal was bad, it wouldn't let you out of park at all.)