Why wouldn't it? It only relies on the ability to create a single outbound TCP connection; surely double NAT doesn't impede that?

If both parties are double NAT, then sure, you have a problem, but aside from that; as long the party you are connecting to doesn't -- it should work fine as described.