lubricate the cable indicated by the red arrows.

on the gearstick end of the cable there is a large fork (that stops your shifter moving when your key is out). If your key sticks again lift the leather gear surround and lift or push down the fork and it should release your key. If this works then look at the image again and to the right of the red arrow (pointing down) is the fork i mentioned with a pin that should move freely (with a spring one side and a retaining clip the other). The fork should move independently of the pin, you will probably find your fork and pin have corroded together so you should hold the end of the pin (the spring end) with some grips and lever the fork in the opposite direction spraying with WD40 or alike and keep working it for a while until loose...

Lubricating it all may just allow the hole thing to move enough for your key to come out a few times and then will resort back to your original issue!

[credit to joe90 and cam-tech-craig]