you have the keys inserted like this:
and yet when you push outwards you say the keys come out?
By pushing outwards you are engaging the little notches on the keys. With the notches clipped onto the HU, you should be able to pull it right out. I would start with the top and pull it a little, then try the bottom. Mine pulled out an eighth of an inch or so on the top, then i pulled it from the bottom
When you put the keys in did you hear any clicking noise, etc?
and I don't know if the icelink is compatible with the iphone. IF the iphone has the same standard ipod connection, then I think you have a pretty damn good shot of getting it to work. Although, I am not 100% sure