O problema parece vir do built-in echo in dash (que é sh no Ubuntu por padrão), que parece processar seus argumentos \ diferentemente de outras implementações ( /bin/echo e echo no Bash):
$ sh -c "echo '\n'"
$ sh -c "/bin/echo '\n'"
\n
$ bash -c "echo '\n'"
\n
Isso não é surpreendente, pois o uso dos argumentos \ em echo não é padrão:
Se o primeiro operando for -n , ou se algum dos operandos contiver um caractere de barra invertida ('\'), os resultados serão definidos pela implementação.
Você deve usar printf em vez de echo , assim:
printf '$template GRAYLOGRFC5424,"<%%pri%%>%%protocol-version%% %%timestamp:::date-rfc3339%% %%HOSTNAME%% %%app-name%% %%procid%% %%msg%% \n"\n' | sudo tee -a rsyslog.conf
Como um bônus adicional, usar sudo tee para gravar em arquivos como root em vez de sudo sh -c + redirecionamentos de shell torna o comando mais limpo, pois a sequência é analisada apenas uma vez (como um argumento para printf ) em vez de duas vezes (primeiro como um argumento para sh -c e depois como um argumento para echo ).