About a year ago, when I still used Gnome (2.4, I think), I had similar problem. I don't remember all the details anymore but I think I did something like this:
First, setuid /sbin/shutdown. (This is a security risk! A safer way is to install Super http://olympus.het.brown.edu/cgi-bin...an1/super.1.gz
and use it instead.)
# mkdir /var/lock/console
# touch /var/lock/console/username
# chattr +i /var/lock/console/username
(where 'username' of course is YOUR username).
Don't know if this works for Gnome 2.6, though. (There may be yet some surprises. I seem to rember Debian wanting to remove /var/lock/console/username during reboots. You just need to work that out yourself.