I had 3 CDs stuck in my CD player last month. To no avail when I pressed eject, they never ejected nor would they play anymore. Eventually after some noise and clicking sounds the message "cd error" would appear every time I started my car. I made an appointment with the toyota dealership to remove them. After waiting 3 or more hours I was told it would cost me approximately 2,000.00 to fix the problem. I said no thanks. After asking around my town, I found a guy who worked at an auto supply store who thought he could fix my problem. When I brought my car in he said my car was very fancy. It has the navigation package in it. He couldn't fix it. I'm desperate now and find someone else who is an expert in installing stereos, speakers, etc. in vehicles, who agrees to fix my car. He thinks he can fix it even though he hasn't installed things in toyotas before. He suggests unhooking the battery from the car for 10 minutes then rebooking it up and pressing the eject button. Well he did but no need to press the eject button. After the car rebooted, The CD player played all 3 CDs then when I pressed eject, they all came out. Charge $10.00. Can you believe that's all it took?
Strange as it may sound, you are not the first person to report something like this. Best of luck to you.
Maybe draw this to the attention of Corporate Toyota, they're getting bad press from that dealership.