Sorry for not getting back quickly, this is partly due to Euro 2004 football on the telly, but mainly due to my slothlike laziness!
I can see what you are saying about different chemistry, but I think (definitely relating to this paper) that this could be a bit of a red herring. For a start the paper is talking about protein motifs, so the period of history they are looking at has chemistry very similar to life today ie nucleic acid encoding for protein.
Although early life (ie before the split between Achaea, Bacteria and Eukaryotes) was undoubtably very 'virus-like' in some ways - like having a small genome and a simple structure - to define this stage of life as being viruses would require a redefinition of what a virus is.
That said, I believe the evidence that viruses evolved early has strong implications for the history of life on this planet. For example, the Woese model of having a pool of many different protocells being the progenitors of the three domains needs an efficient method of horizontal transfer - viruses are great candidates.
Not quite the universal role for viruses envisaged by SUnderwood (I'm not sure, but I think genetic studies would have picked up the significant events he's talking about), but a vital role non-the-less!