I have sent a transaction to mtgox, blockinfo reports that the network fee is lower than recommended, so it will take quite a long while to get confirmed.

I was thinking I can send another transaction with more attractive fees - but that represents two difficulties:

•     I don't know why the client didn't calculate the correct fee
  
•     mtgox uses a single address per transaction, and so I won't get a new one until the current one completes. If I send another transaction to the current address, when the slow one finally gets there, it will go to the wrong address.
  

I am not sure what is the best way forward. I am using bitcoind v80500.

Is there a way I can get a transaction into mtgox without breaking the one I have currently waiting for confirmation, and if so, how can I get the fees to be right?