Mike,
You may also have to "fiddle a little bit" with sliding the gear back and forth a little. I had the same problem when I changed mine and installed the Ford Crown Vic solenoid. It didn't seem to want to come out or maybe I was having a hard time getting the replacement in place. After reaching into the nose of the starter and pushing the gear back and forth, everything matched up and it went in (or came out).
FYI, I replaced mine after about 500 hrs after it would not always engage and almost acted like a bad battery. Sometimes just "click" a few times before engaging. The solenoid itself seemed to have worn where the electromagnet slides in a sleeve. After I got it out and played with it, I could see how sometimes it would engage forcefully and other times not so much. After replacement I never had a problem. Depending on cowl removal issues and how long that takes, it is a 15 minute job to just replace the solenoid.
Keith