Os erros são devidos a alterações no novo rsyslog.
Em /etc/default/rsyslog , comentei a linha:
#RSYSLOGD_OPTIONS="-4 -x"
Onde x estava lá por padrão (eu acho), e -4 era uma adição minha.
Eu adicionei em sua substituição para /etc/rsyslog.conf :
net.enableDNS="off"
net.ipprotocol="ipv4-only"
No Debian com backports completos, isso não acontece, já que rsyslogd com esta configuração foi backportada para o Debian 8 há algum tempo.