I too learned the hard way that on Relist or Sell Similar, ebay will sometimes change your shipping options on the item you're selling to the most recent shipping options you used for something different.
Ultimately, however, it is the seller who is responsible to take note of that before hitting List.
I think you are stuck shipping it for free to the buyer if that is how it sold. It's not the fault of the buyer that your item was mixed up when it got listed. They purchased, they promptly paid, they have every right to expect they get something in return.
Ship it, accept the loss, and then try to convince ebay it wasn't your fault and they might give you your money back.If you are very persuasive and/or lucky.
Alternatively, cancel it and accept the defect and/or feedback that follows. I think this is one of those times where you have to decide what the sale is worth to you versus what damage it might do to your selling standards should you cancel it.
The only thing that might change my advice is if another 29 sellers come forward today to say the same thing happened to them. Like it's a wide-spread 'free postage' glitch. I sold something last night too for FREE POSTAGE that I don't exactly recall as having free postage on it but I cannot be 100 per cent positive of that until I look at the copy I made of the original listing to see if it says it ships for free.