I have never used gksu or gksudo because the terminal works fine for me, but I have a suggestion:
Try running gksu in debug mode; man gksu will tell the argument to use. Maybe that will throw a useful error message.
The man page also says:
Notice that all the magic is done by the underlying library, libgksu.
Also notice that the library will decide if it should use su or sudo as
backend using the /apps/gksu/sudo-mode gconf key, if you call the gksu
command. You can force the backend by using the gksudo command, or by
using the --sudo-mode and --su-mode options.
Since gksu will decide whether to su or sudo the command, check whether your user name is in the sudoer file and, if it is not, try putting it in there and see whether that makes a difference. (Use visudo as root to edit the sudoers file.)