O próprio regex funciona bem, como mostra este exemplo do Python:
import re
print re.sub(r"(<font color=.+?>JohnDoe</font>)",
r"<span class=myclass></span>",
"<font color=#FF4AFF>JohnDoe</font>")
# Prints <span class=myclass><font color=#FF4AFF>JohnDoe</font></span>
(supondo que o Privoxy use a mesma sintaxe regex, exceto a diferença vs.
$1
, mas parece que sim.)
Eu acho que o problema está em outro lugar - tente um regex que não pode falhar, como substituir a
por b
, para ver se está tendo algum efeito.