shutdown is usually in /sbin/, which is not in users' PATH, which is why it said command not found.
Code:
user$ which shutdown
which: no shutdown in (/usr/lib64/mpi/gcc/openmpi/bin:/home/user/bin:/usr/local/bin:/usr/bin:/bin:/usr/bin/X11:/usr/X11R6/bin:/usr/games:/usr/lib64/jvm/jre
/bin)
user$ su -
Password:
root$ which shutdown
/sbin/shutdown
Try running "sudo /sbin/shutdown -h now" and see what happens