Make sure the mechanical pieces are moving properly to release the shifter position lock when you press the button in. Mine fell apart once.
Use process of elimination to problem solve: Disconnect the cable from the shifter to see if the shifter itself works well. Try the cable by hand to see if that works too. You can even disconnect it at the trans and try moving it. This should give you an indication of the problem.