Functions which provide the output are installed to the
/lib/lsb/init-functions.d directory. Most likely you do not have anything there which provides the nice output.
lsb-base package provides the
/lib/lsb/init-functions script which is sourced by your init script. This provides stubs for the functions that produce the output which are overridden by sourcing each file in
Scripts providing these functions should be put there by some package installed as part of your startup system. For example I have
systemd on Debian Jessie which provides
/lib/lsb/init-functions.d/40-systemd. This outputs a slightly different message when restarting services. For
ssh I get:
[ ok ] Restarting ssh (via systemctl): ssh.service.
Most likely you either do not have the correct package installed, the files have somehow been deleted or there is a bug somewhere in the version of the package you are using.
grep -r Restarting /lib/lsb on both systems to find the file which produces the message (if there is one). You can then use
dpkg -S <filename> to find the package that installed it.