I am not sure I believe their theory. It is also possible that people brought the disease to the new world. There is quite a bit of circumstantial evidence for human travel across the Atlantic by the Phoenicians and/or Romans. It is unlikely there was any regular trade, but over the centuries a few ships may have been blown off course, and made a one-way trip. For instance, the bottle gourd, which was used to store water on ships, crossed the Atlantic to Brazil right about that time. Most likely the seeds were brought there on a ship.
That would be easy enough to test, provided we had archeological samples of Phoenicians / Romans who were infected with M. tuberculosis (Mtb). Then, one could do the same phylogenetic analysis done in the paper that claded with the seal / sea lion Mtb sequences. Of course, the sequence analysis data provided in the paper would probably argue against your hypothesis, as Mtb sequences obtained from infected members of those civilizations would probably clade with modern European Mtb sequences rather than with seal / sea lion Mtb, which it would have to do in order to fit the data in this study.