heathen
The following is extracted from the Catholic Encyclopedia online. http://www.newadvent.org/cathen/03449a.htm. 4 October, 2004.
"the combination "the catholic church" (he katholike ekklisia) is found for the first time in the letter of St. Ignatius to the Smyrnaeans, written about the year 110. The words run: 'Wheresoever the bishop shall appear, there let the people be, even as where Jesus may be, there is the universal (katholike) Church.' "
There are other mentions of the word Catholic, in reference to a religion, as ealry as 155 and 180AD. Clement of Alexandria said sometime after 180 that, "that both in substance and in seeming, both in origin and in development, the primitive and Catholic Church is the only one, agreeing as it does in the unity of one faith"
By reading further on in the encyclopedia it seems apparent that the term Catholic, in reference to the religion, was clearly established by the beginning of the 3rd century, and most certainly prior to, and perhaps as early as 110AD.
Hope this helps.
Hondo