It wasn't merely the fact of teaching for those outside the aristocracy but also the content and purpose of such teaching that undermined the established order. As I.F. Stone puts it in The Trial of Socrates,
There is a strong element of class prejudice in the Socratic animosity towards the Sophists. They were teachers who found their markets in democratic cities like Athens among a rising middle class.... They wanted to be able to challenge the old landed aristocracy for leadership by learning the arts of rhetoric and logic so they could speak effectively in the assembly.... [H]igher education remained the monopoly of the aristocracy until the Sophists came along. They provoked upper-class antagonism by teaching the arts of rhetoric-- for an ability to speak well in public was the open door to middle-class political participation in the debates of the assembly and the higher offices of the city.Sophists also threatened through the radicalism of their teachings. Although ancient Athenian religion was never as prescriptive or rigid as the monotheistic religions tend to be, the profound agnosticism found among major Sophistic thinkers like Protagoras must have rankled Athenian society. The Sophists also posed radical critiques of the meaning of knowledge and existence of truth, topics which provoke reactionary responses even today. Alcidamas of Elaea expressed the earliest known condemnation of slavery in human history, in a time when slavery was an essential part of the economy and the social structure. In every sense, the Sophists represented an intellectual tradition that challenged the status quo.
It's therefore no surprise that they have been shrouded in mistrust and dismissal by history. For centuries, the Sophists were dismissed as deceitful and illogical. Even today, "sophistry" is a term that refers to weaselly, conniving discourse. Rhetoric itself labors in an assumed worldview that distrusts it, under the inherently reactionary theory that the truth can be articulated plainly without the need for ornamentation. It's no accident that this long tradition of disrespect stands in contrast to the reverence for Socrates and Plato-- two explicitly anti-egalitarian thinkers who expressed a longing for authoritarian power and a distrust of the common man. Those in power write the history, and its up to us to recognize, even 2,500 years later, those whose arguments were belittled and misconstrued because they challenged the current power structure. And it behooves us to recognize one of the constants of human history: the power and persistence of class struggle.