O Debian usa o rsyslog por padrão agora ao invés do syslogkd (que eu tenho certeza que você está procurando, não apenas "syslog"). Este tem sido o caso desde Lenny.
Se não estiver instalado, instale o rsyslog. É um substituto para apenas o syslog normal.