Let me reassure you that computational biologists who do these kinds of analysis are very aware that evolution is not linear (hence the many methods for building evolutionary trees), and that similar mutations could (and do) occur in different branches of a tree. The argument being made here is that something new has appeared -- there are many new trees that emerged about 650 million years ago. (In the protein world, 650 million years is a relatively short time, so evolutionary relationships at that distance should be detected.)
That said, it is very dangerous to talk about "novel genes" or "novel proteins" without being very clear about the nature of the novelty. Just as protein sequence comparison is more sensitive (has a longer evolutionary look-back time) than DNA sequence comparison, there are methods (not used in this paper) that can look back even farther, and we know that there are ancient evolutionary relationships that are difficult to recognize using sequence comparison, the approach used here. Moreover, many proteins are build from modules (called domains) that can be rearranged, so even though the module might be old, the particular arrangement might be newer. After a quick scan of the paper, it was unclear to me whether the authors are claiming that there are a large number of genuinely novel domains (unlikely), or simply arrangements (more likely), or perhaps simply duplications of existing genes (very likely, but not very novel).