What “slot” are we talking about in your car stereo? Single CD slot, a multi-CD changer, a cassette slot… 8 track?
I’m guessing the reason he’s quoting so much is that he’s basically planning on removing your head unit, then shake the coin free (possibly needing to partially disassemble it), then re-install it into your car. So the labor charge is roughly equivalent to removing and installing a head unit, and $250 seems to me to be on the high side for that, even in a high cost area such as L.A. Experienced people swap these things in and out like I could swap out hard drives.
I think he’s really trying to convince you that as long as you’re ponying up the labor cost to do this, you may as well also buy a new head unit, add an iPod connector, etc. Which may be true. If you’re still using your “factory” head unit and it doesn’t have features integrated into your car, like climate control or GPS functions, maybe you COULD take this “opportunity” to upgrade.
Otherwise, I’m not convinced such all-out effort is necessary. Have you tried taking it to your dealer for servicing? Or if you want to try it yourself, try Googling your car’s make/model and add the keyword “head unit removal”, you might find a helpful link. Or check out Crutchfield’s guide to car stereo installation (Step 1 of which is, of course, “remove the old stereo”).