A google search on the term also brought up this site, which even at a glance is clearly working within a New Testament tradition, and offers a completely different take on the meaning of paideia.
What jumped out was how this shift from the normative, Greek sense of the term into its New Testament transformation is situated, by the site itself, in the text of Paul:
Thus Paul, in Ephesians, instructs fathers to raise their children in the “paideia of the Lord,” preparing them to be faithful citizens in the kingdom of God and preparing them to engage the enemy with the transforming gospel of Jesus Christ.The difference between the two uses of the word is stark, and radical. For our "big picture" interest in the differences between the Hebraic and the Greco-Roman traditions, it might be seen as an epitome of what we have been finding in our readings.
This brief overview offers a bit more detail on classical paideia.