O Debian 8 usa por padrão systemd como seu sistema init, enquanto as versões anteriores usavam sysVinit . Assim, você precisa usar diferentes maneiras de reiniciar os serviços.
Use systemctl [start|stop|whatever] something , não service .
A reinicialização ainda deve enviar uma mensagem. Experimente shutdown -r (o comando reboot é um comando de compatibilidade legado com o systemd e pode desaparecer no futuro).