As funções que fornecem a saída são instaladas no diretório /lib/lsb/init-functions.d . Muito provavelmente você não tem nada lá que forneça a boa saída.
O pacote lsb-base fornece o script /lib/lsb/init-functions que é originado pelo seu script de inicialização. Isso fornece stubs para as funções que produzem a saída que são substituídas pelo fornecimento de cada arquivo em /lib/lsb/init-functions.d .
Os scripts que fornecem essas funções devem ser colocados por algum pacote instalado como parte de seu sistema de inicialização. Por exemplo, eu tenho systemd no Debian Jessie que fornece /lib/lsb/init-functions.d/40-systemd . Isso gera uma mensagem ligeiramente diferente ao reiniciar os serviços. Por ssh eu recebo:
[ ok ] Restarting ssh (via systemctl): ssh.service.
O mais provável é que você não tenha o pacote correto instalado, os arquivos foram de alguma forma excluídos ou há um bug em algum lugar na versão do pacote que você está usando.
Tente fazer grep -r Restarting /lib/lsb em ambos os sistemas para encontrar o arquivo que produz a mensagem (se houver). Você pode então usar dpkg -S <filename> para encontrar o pacote que o instalou.