doing an rpm -qf /usr/bin/shutdown reveals that /usr/bin/shutdown is owned by the SysVinit package. ldd reveals that /usr/bin/shutdown is linked against libgdk and libgtk. /sbin/shutdown, fortunately, does not suffer from this. Furthermore, SysVinit does not depend on any package that contains gtk+. This seems broken to me. Certainly the dependencies are broken, and most likely so is the fact that /usr/bin/shutdown is linked against libgtk and libgdk.
This issue has been forwarded to a developer for further review.
The short answer is that /sbin/shutdown is the beast you want, not /usr/bin/shutdown. Here's my best guess at the longer answer: The file /usr/bin/shutdown is a symlink to consolehelper which does not only shutdowns but other PAM console functions. Some of these functions require changing the controlling tty and updating utmp entries. These operations are implemented using the gnome-terminal abstraction which needs gtk.