Last night MtGox re-queued my transaction and this time it went through.
Thanks for the update and I'm glad they took care of your issue. I've had no such luck yet with mine, but I hope the fact that yours was resolved means mine will be soon. Did they write you an email telling you they requeued or anything? I still haven't heard from them since they asked for the transaction id.