Возможно, ваш интерпретатор PHP не работает как пользователь с соответствующими правами для этого. Обычно это нужно делать с правами суперпользователя, что в целом является плохой идеей для PHP, поскольку одна маленькая дыра в безопасности может привести к взлому всей машины.
Если вы действительно хотите сделать это, я бы посоветовал рассмотреть возможность использования sudo для предоставления ограниченного дополнительного доступа пользователю, от имени которого работает веб-сервер.
Другой альтернативой sudo в некоторых системах является dbus. С правильными привилегиями dbus вы можете отправить инструкцию на перезапуск, например,
dbus-send --system --print-reply --dest="org.freedesktop.Hal" /org/freedesktop/Hal/devices/computer org.freedesktop.Hal.Device.SystemPowerManagement.Shutdown
Работает из командной строки, и я считаю, что для php доступны привязки dbus.