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.