I have looked around for a fix to this (google, forums, Ubuntu Wiki) but had no luck.
It may be some bug or it may be that some file somewhere didn't get updated properly, you could try
sudo apt-get dist-upgrade
to make sure all the files are upgraded.
Then give it a go. "gksu gedit"
If it still won't work you could try removing the sudo package and the reinstalling it, but make sure you set the root password first:
then set the password for root.
#(type the password you just set)
apt-get remove sudo
It will show a list of packages that will also be removed and ask if you want to continue, make a note or them so you can reinstall them and answer yes.
apt-get install sudo
apt-get install (the list of packages that were removed)
apt-get install gksu ubuntu-minimal
the "apt-get clean" makes sure it downloads the package from the ubuntu server by removing the archive files from the cache.
Other than that I really have no idea.
I was using Ubuntu from the 5.10 (Breezy) cd and when I updated it worked fine, now I'm using Kubuntu from downloaded 5.10 (Breezy). KDE uses a different command to use a program as root (kdesu) and have had no problems, so you could install KDE (BIG download) and use that with gnome. I think that could work, or if you don't want all of KDE's stuff try just getting "kdebase-bin" and it's dependencies.