In ancient Roman slang, “pagani” didn’t just mean “countryfolk”. It was military slang for “civvies”, the people who stayed home on the farm while you enlisted, or the people out in the countryside who your squad wasn’t supposed to antagonize while you marched through the Roman world. (See definition 2 in the link.)
So why was this picked up as Christian slang for non-Christian worshippers of the various gods? Because Christians were urban and countrydwellers were hard to convert? I now think that’s probably not what happened, in light of the military slang. No, I think it’s an old joke that goes something like this:
Roman recruits took an oath (sacramentum) and became legionaries. Catechumens took the covenant oath act/sacrament (sacramentum) of Baptism, and became Christians. So obviously, Christians were in Christ’s legion, and non-Christians were civvies. 
But it was even more useful than that. Jews were part of the older covenant oaths of God, and so were clearly not civvies. This meant it wasn’t simply a cliqueish term for “those people over there who aren’t part of the Church”, but had wider application. It also implied a sort of protectiveness. Christians had been made the salt of the earth and the light of the world, for the benefit and defense of the civvies from the attacks of the enemy, the Devil.
From very early on, there were buttloads of military folks who (by the archaeological evidence) were buried as Christians, as well as all the legendary evidence to the same effect. We know they influenced religious discourse in some fairly important ways, like ending the Mass with the military command “Ita, missa est!” Imbedding a joke like this would be quite logical.
I’ve probably read this somewhere before, but it didn’t stick. I don’t remember Scott Hahn on “pagani”, although he talks a lot about “sacramentum”. Robin Lane Fox mentioned the military meaning in his 1980′s Pagans and Christians book on the transition of the Roman world to Christianity (which I’ve been reading), and says it was never formally used in formal early Christian texts like Bible translations.
UPDATE: Apparently Robin Lane Fox talks about this more, later in the book. His rationale is apparently centered on the early Christian image of themselves as “milites Christi”, soldiers of Christ, and not on “sacramentum”. But I have to get to that point in the book to see what’s going on, and if more is mentioned.
Also, apparently I missed talk about this on the etymology site Take My Word for It back in 1999, which was reprinted several places on the Web, and which apparently drew its info from Robin Lane Fox. Aeh, I’m always last to know.
