So why does nxt have this problem too? Is this something inherent to crypto currencies?
Can it be fixed?
Will it be fixed?
What should exchanges rely on instead of transaction Ids / transaction bytes?
It is due to the way a tx is constructed and hashed - if the signature(s) do not include every byte of the transaction then it will always be possible to modify the tx and if the hash is of the entire tx (not just the signed part(s)) then there is not much you can do about it apart from:
Don't rely upon the tx hash (something Mt. Gox should never have been doing in the first place).
Nxt does actually make things simpler in that you can just use Account #s (you don't have to deal with UTXOs).
An exchange should only display a txid *after* the tx has been confirmed (until then it should just be displayed as "unconfirmed" with no hash at all) and even then the txid should only be handled as "descriptive" data (i.e. not indexed for any important purpose).