O Gedit simplesmente interpreta o caracter \n como nova linha, o que é correto e útil na minha opinião, porque permite substituir algo por quebras de linha reais.
Para parar e substituir algo com \n literalmente, você tem que escapar da barra invertida com outra barra invertida e digitar \n no campo de texto "Substituir por".
