Does anyone know good software for producing tanglegrams?
Dendroscope

Using Dendroscope, I opened the provided example file trees.new. This opens a new window with 16 trees in it.


Shift click on the first two trees (Tree1 and Tree2).
Choose Algorithms $\rightarrow$ Tanglegram...
This will compute the tanglegram and open a new window.


At this point, I get:



There is nothing special in the trees.new file, just 16 Newick trees. So it looks like all you need is to have your trees in the same file or use File $\rightarrow$ Add from file. 

I think that the tricky part is that your trees have to have the same tip labels, so that they can be lined up optimally. So in your example, Phalacrocorax pygmaeus and Pectinopygus excornis must have been named the same in the original Nexus file and then modified to produce the final figure.

TreeMap 3

TreeMap requires some preliminary setup. Basically you create a Nexus file manually. Using the 4taxonmatch file from the examples, you can get the basic layout. You have a HOST block and a PARASITE block. Within each one of those is a TREE block, which contains the Newick formatted tree.

The RANGE block inside the DISTRIBUTION block contains the mapping table. Here p maps to u, etc. This is the connection between host and parasite.

#NEXUS
BEGIN HOST; 
TREE * Host1 = (u, (v, (w, x))); 
ENDBLOCK; 

BEGIN PARASITE;
TREE * Para1 = (p, (q, (r, s))); 
ENDBLOCK; 

BEGIN DISTRIBUTION; 
RANGE 
    p: u, 
    q: v, 
    r: w, 
    s: x
; 
END;


In contrast, you get the correctly labelled tree directly. See below.