We just had this issue and got some more information.
It's my wife's car, 2009 Mazda 5 that we bought in September 2009. The phone is a LG Chocolate Touch that she bought last week. First time in the charger - stuck. I'd like to complain to Verizon about this. We went to the Verizon store in Union, NJ, and the store manager, David Rivera, said he had never heard of this before. He said their insurance didn't cover them to look at a charger in a car, so he couldn't help us. Told us to call a mechanic. I asked if he'd refund the charger if it was destroyed. He said yes. I asked if he'd pay the cost to remove the charger, and he said they had to look at it first.
I called the Mazda dealer in Union, NJ. Really helpful, said I was about the 15th or 20th call. Took it over there. He called his other technician. They pulled the entire charger power socket unit out pretty easily. Then together, I think using a screwdrivier, they removed the charger from the cigarette lighter. They showed me that the clips were too big. They, like others reported here, said that Mazda has not issued a bulletin. However, they shared a 2000 bulletin about the size. They said it is only a problem with newer Mazdas. He said that he bought a charger from the local convenience store instead.
we then took the charger back to Verizon and returned it, and then bought one from Wal-Mart.
I guess Verizon's "it's not my problem," attitude really got to me. I think Mazda's tolerances may have been more forgiving before, but now they are not.