Store the original transaction id, and (amount, timestamp, dest address).  Assign "in" and "out" bitcoin addresses to each account.

All withdrawals will come from "out" address to "dest" (end user, private) address.  If someone changes the original transaction id, no problem.
Use the "out" address, timestamp and amount to find the changed transaction id and validate the transaction.
Store the modified transaction id along with the original transaction id.

If someone comes along and claims that they did not receive funds, check the list of transactions, if more than one, flag the user.

I think what happened was that their system was looking for the original transaction id in the block chain, and if not found their system was
automatically initiating another transaction to the same dest address.  I say their system did not handle this "not found" error properly.

Claiming that the protocol needs to be changed is a bit extreme.  I hear this all the time from "not so hot" developers.  
"The problem is not in my code.  It is not me, it is xxx/so and so.  Excuse after excuse.  My code is perfect, if you want to work with my module, change your interface, blah, blah"

They want bitcoin to change the protocol so that their system works.  Well, they should change their system so that it works with bitcoin network, not the other way around.

I think Mt.Gox should close the doors after this.  They would save their face, if they came out and said "yes, we've had a bug in our code.  We'll fix this in two days."
That would give them some credibility.  Now, they look like "not so hot" developers.

If they cannot handle errors in their system, I wonder how stable their trading platform is?