The tire could also be out of round, in which case they can shave it to make it possible to balance (taking a few K miles with it). No matter what it is, a skilled tire shop should be able to take care of it. They should also be able to handle any warranty available from the tire manufacturer.
Do you have the OEM Michelin Energy Savers on the car?
Do you have the OEM Michelin Energy Savers on the car?