"There is no sound etymology for this word, which appears only in Portuguese, Catalan, Galician and Spanish (other romance languages use words derived from Latin strix, -igis, originally an owl or bird of evil omen). The word may be inherited from aCeltiberian substrate or it may derive from the Latin plusscius, -a, um (> plus + scius), a hapax attested in the Cena Trimalchionis, a central part in Petronius' Satyricon. Pluscia could have arisen from rhotacization of the /l/ and voicing of the /p/, pluscia> pruscia> bruscia> bruxa (Portuguese)> bruja (Spanish)."
While a definitive etymology of "bruja" has not yet been demonstrated, interesting and perceptive possibilities, such as the pluscia > bruja described above are of interest, but not definitive. The problem with the hypothesis is that the author offers no evidence from literature of the intermediate steps that are hypothesized. Additionally, the positing of the putative /pl-/ evolving to /br-/ defies the more common pathway in which Latin /pl-/ > Castilian /palatalized l/, as in Latin "plenus" evolving to "lleno." /pl-/ may have evolved differently in other dialects of Spanish, as Rafael Lapesa has demonstrated in his Historia de la Lengua Española, but that complicates this questionable phonetic development even more.
Let us examine the far more proven evolution of a markedly important Spanish word from its medieval source. The slow but steady development of Middle Spanish "vuestra merced" (your grace, your majesty) to "usted" is proven by evidence from literature of many of the intermediate forms (vuestra merced > vuessa merced > vosarced > vuartsed > vutsed > utsed > usted). That particular example is fortuitous in that the word for "you" is clearly a very common locution and one would expect to see many examples of this over the centuries. However, "bruja" is not so common a locution and thus there is far less opportunity to follow it through the centuries. The indisputable Dean of Spanish etymology, Joan Corominas (ref. to be supplied shortly), himself says it is of uncertain origin.
If Corominas and other Romance linguists were familiar with Hebrew, they might have plumbed the history of Jews in Spain and possibly solved this seemingly intractable conundrum. They would have come to realize that in the minds of many Spaniards of the age of Fernando and Isabela and their predecessors, Jewish religious practice was viewed with a range of feelings ranging from curiosity to deep suspicion, fear, and even to rank hatred. Those Spaniards who might have heard Jews at prayer would doubtless hear the opening words of most prayers: "Baruch ata Adonai Eloheinu, melech ha-olam..." (Blessed are you Lord our God, king of the universe...") The spelling "-ch-" is pronounced almost exactly as the faucal voiceless fricative represented by the Spanish letter "j". So, the first three syllables of "Baruch ata" doubtlessly would sound to a Spaniard like: "Bruja" Thus, the Jews might become known in popular parlance as the people who say: "Bruja" when they pray. It is easy to hypothesize that in the Spanish mind "bruja" must be the word that Jews use to characterize themselves. Since many Spaniards considered Jews to be evil, even of Satan, the word became associated with hechicería (a synonym of "brujería"). It is reminiscent of the error the Romans made when, upon first landing in a cove at the tip of Southern Greece, they encountered a small tribe who called themselves "Graeci," and made the error of assuming that therefore, all natives of this country were "Graeci," hence the name by which they came to be known to the Romans, rather than "Hellenes" which is what most of the natives called themselves. A similar error was made by the Spaniards who called the natives of the New World "indios," thinking they had reached India; and that error stuck too, enshrined by tradition and ultimately by history and yet another such error was made in Central Mexico when the Spanish colonizers happened upon the indigenous Huichol tribe in what is now the state of Michoacán. When they married the native women, their families called the Spaniards "tarascos," meaning "brother-in-law," but the Spaniards thought they had just been inducted into the tribe of Tarascos and that now they, too, were Tarascos. Thus, the Mexicans to this day call the Huichol natives by that ancient misnomer.
In sum, given the weakness of any of the extant etymologies of "bruja" and "brujería," I would suggest that etymological investigators give the same consideration to this hypothesis as they give to hypotheses suggested elsewhere.