O problema está nas permissões do usuário APACHE.
Você pode dar permissões sudo ao seu script, o que não é a melhor idéia, em termos de segurança.
Ou use ssh2_connect
para conectar-se ao seu servidor com ssh e executar apenas useradd como root.
$connection = ssh2_connect('localhost', 22);
if (ssh2_auth_password($connection, 'root', '')) {
$username = 'username';
$password = 'password';
ssh2_exec($connection, "useradd $username -m -p $password -d /home/$username/ -s /bin/false");
} else {
die('Authentication Failed...');
}
Veja ssh2_connect e ssh2_auth_password docs.