Isn't it the case that the other coin-swapping protocols are susceptible to this same weakness? This applies generally to double-spends too. The cost of mining a big-enough "attack fork" can be amortized over many concurrent double-spend attacks using the same attack fork.
Yes, you're partially right, but I think there is at least one key difference. The difference that comes to my mind is the "visibility" of the attack event:
in TierNolan's protocol the attacker would need to create a long fork that everyone will see and that will become the best chain, and that will roll back tens of thousands of normal transactions, and that will destroy the credibility of one of the cryptocurrency involved. So the attack cannot be profited: if the attacker tries to cheat and get the coins of both cryptocurrencies in the trade, one of them will loose completely its value, so there is no incentive for the attack. Also the attack cannot be repeated.
In p2ptradex you may do it without affecting the users of the BTC side of the chain. The attack will just prove that with enough incentives an attacker can "hire" mining power and execute the parallel attack and build a competing block branch, but without actually putting this branch "life". If does not need to be the best chain. The fake chain will only be used to prove other users that certain transactions were done, when in fact they weren't. This does not destroy the credibility of the system, but just proves that the users did not paid attention to the recommended maximum trading limits, and made risky operations.
Iit has to be carefully analyzed in TierNolan's protocol what's the effect to forking at each protocol step, but I think that in every possible attack the attacker must build and publish his own long best chain.
Also in both protocols there is the possibility of a miners-conspirancy not to include certain "redeem" transaction, but this will require almost all miners to be part of the clan.