What is the time line from the marriage to the honeymoon? If you have time, I think you just go back and take another lap with BA or QF after the wedding and after you have the marriage certificate.

That time around, you have the Mrs. call up and state a little more matter-of-fact that she got married, changed her name, has her marriage certificate and needs to change her name on a ticket.

I think you'll get a different reaction due to the slight change in circumstances and attitudes. A little less "how do we change a name for this future situation that hasn't happened yet" and a little more "my name is changed, I have legal documentation, you need to update your system (FF account, issued tix) to reflect that fact."