When you push the release button next to the shift lever , make sure your not trying to squeeze the button on the shifter handle at the same time. that can prevent it from releasing. If , when stepping on the brake pedal , you do have brake lights , but you don't hear the 'shift lock solenoid' clicking you either have a bad connection (wire or plug) , or there may be a problem with the PCM or 'gear selector switch' (range selector switch). Reply with results or other symptoms for further diagnostic tips.
The ignition switch is not the problem. The shift interlock SYSTEM is the problem. If the PCM does not see your foot on the brake(IE FAULTY BRAKE SWITCH) it will not send the signal to the shift lock soleniod to 'release'. IF I'm wrong ....reply and tell me I'm an idiot! (won't be the first time)