I've only had this happen to me once, and I solved the problem pretty easily. The bottle we ordered was obviously corked, and I told the waiter, who looked nervous, then summoned the manager. The manager poured a glass, sniffed it, and said, no it's fine. Remaining calm, polite, but somewhat amused because the wine smelled like an old sweatsock wrapped in moldy cardboard, I said to him that he should probably try it again.

When he once again insisted the wine was ok, I told him that I would make a deal with him: Bring me a new bottle of the wine, and if it's the same as the original bottle, I would buy both of them. If, however, there was a noticeable difference, proving that the first bottle was indeed corked, then HE would buy both of them.

He looked at me for a minute, took the bottle away, brought us a new one, which was fine, and I paid for it with no further drama.