Ciao,
così a naso mi sembra che sia un problema di permessi, ovvero il tuo utente può eseguire lo script da te creato (per questo vedi la echo) ma non hai i permessi per lanciare uno shutdown.

Tieni conto che i comandi lanciati da php generalmente hanno come utente di sistema quello di apache, per cui mi sembra logico che tale utente non possa fare azioni delicate come il riavvio di un sistema.
Per sicurezza verifica con questa pagina quale utente stai usando
Codice PHP:
<?php
// outputs the username that owns the running php/httpd process
// (on a system with the "whoami" executable in the path)
echo exec('whoami');
?>