The problem might also be on the mechanical side of the ignition-- if the shift interlock mechanism is gummed up near the shifter it can result in mechanical interference with the cross shaft that goes into the electrical part of the ignition.

You could check for this by removing the cladding underneath the steering wheel, putting the key in the ignition, turning it to key pos 1, then temporarily removing the shift interlock cable by squeezing the clip and pulling it out. If the starter disengages properly, you've found your culprit, and can clean it up/adjust it, then put it back together.

Good luck!