Substitua service pelo caminho completo para service binário, ou seja, /usr/sbin/service :
#!/bin/bash
if ! [ "$(ping -c 1 google.com)" ]; then
/usr/sbin/service network-manager restart
fi
Também coloque isso em root crontab , como reiniciar network-manager requer root privilégio, alternativamente, você pode conceder a si mesmo sem senha sudo acesso somente para este comando, então você pode usar sudo /usr/sbin/service network-manager restart .