No sure about the GNOME error you've apparently encountered, but it is possible to put that shutdown command into a script file, and call that from a KDE icon - so maybe you can do something similar in GNOME.
I. e. in KDE you would
1. Create a text file using vi, emacs, kate, or whatever text editor you prefer, and call the file stop.sh
Put this inside it:
sudo shutdown -h now
2. Save the file in your home directory.
3. Unlock the KDE desktop widgets
4. Press ALT-F2 to bring up the quick execution bar
6. Click on New
7. Select an icon for your new button by clicking on the icon button
8. Go to the "command" or "application" tab.
9. In the line where you can enter the name of the excutable to run if that icon is clicked, type
sh -f /home/your_home_dir_name/stop.sh
11. Click and drag that icon from the kmenueditor's list to the taskbar and move it into position
12. Close kmenueditor
13. Optionally, relock the desktop icons.
If you now click on the icon you just created, it should call the stop.sh script, which contains sudo shutdown -h now
which should shut down your system. I. e. you'll mostly have the functionality back of having a single button you can click on to shutdown your system. You can also, of course, make your own "reboot" button, just change the -h to -r, as you already indicated.
Note that doing it this way -might- bother some KDE programs (for example, in FC10, doing a shutdown -h now instead of the normal "logout" on my system, would make some KDE stuff complain on the next startup, but nothing serious)