Beware that half a million years is Cabot's vs. Elegant. Not Cabot's vs. Sandwich -- this would be closer to 3 millions.
Given how widespread orange/yellow bills are in
Thalasseus terns, and the absence of suggestion that they might be limited to a particular subclade in the group, I would expect this to be the ancestral state. If so, what you'd have to explain would rather, arguably, be
black bills (with a yellow tip) having apparently evolved twice on different continents -- once in Sandwich, once in northern Cabot's.
There are mtDNA data for Cabot's Tern from USA (North Carolina, Florida, Louisiana), Guyane Française (in the BOLD database, still private, but position assessable from ID trees), Brazil, and Argentina. These all show the same pattern: all these birds are closely inter-related, and form a group which is closer to Elegant than to nominate Sandwich. (These aspects of the phylogeny are certainly
not "not well resolved".) (Two slightly divergent haplogroups seem to be present in Cabot's, however; one of them occurring in all populations; the other (so far) limited to
acuflavidus, where it occurs in admixture with the first one.)
(The mitochondrial sequences used in Collinson et al were taken from GenBank; the
T. a. eurygnathus in Fig. 1 (DQ385180, voucher "G12325" -- same bird as in
Given et al 2005) was from Salinas, Brazil; the three birds in Fig. 2 were from Escalvada Is. (FJ356224), Para (AY631375), and Salinas (DQ385095, same bird as in Fig. 1), all in Brazil. Fig. 4 is less straightforward -- Collinson et al cited
Dufour et al 2017 as a source for the nuclear sequences they used; but Dufour et al 2017 used sequences from
Efe et al 2009 for
eurygnathus; Efe et al 2009 had three
eurygnathus from Escalvada Is., Brazil, and two from Punta León, Argentina: I would expect the
eurygnathus in Fig. 4 of Collinson et al to be among these five birds; the trouble is, there are only three of them, and I can't tell which ones they are.)