I was having this problem on Ubuntu 12.04 (precise), but most of the Google results pointed to a bug in Hardy. However there are other causes of this problem.
In my case it was a previously-created share with a different user ID – Nautilus couldn’t create the share because there was already a share file with the same name owned by a different user.
The directory is /var/lib/samba/usershares. You should already have write access assuming you’re a member of the sambashare group (which the gui should handle for you), so all that remains to be done is remove the offending share with the same name as the one you’re trying to create.
alex@al4:~$ cd /var/lib/samba/usershares/ alex@al4:/var/lib/samba/usershares$ ls -lah total 16K drwxrwx--T 2 root sambashare 4.0K Jul 25 12:33 . drwxr-xr-x 5 root root 4.0K May 1 10:40 .. -rw-r--r-- 1 2046297271 2046296576 142 Oct 25 2011 music -rw-r--r-- 1 2046297271 2046296576 128 Feb 7 17:13 videos alex@al4:/var/lib/samba/usershares$ sudo rm music [sudo] password for alex: alex@al4:/var/lib/samba/usershares$ sudo rm videos alex@al4:/var/lib/samba/usershares$
After doing the above, Nautilus was able to recreate the shares without trouble.