To enable menu editing per user config (via nautilus), you need to open a terminal and do the following:

$ su -
 <give root password> 

# cd /etc/gnome-vfs-2.0/modules
# cp default-modules.conf default-modules.conf-no-menu-editing
# cp default-modules.conf.with-menu-editing default-modules.conf                                

For any user you want to have the right to edit their menu, you also need to do this as the user:

$ cd ~/.gnome2/vfolders                                
$ cp /etc/X11/desktop-menus/applications.menu applications.vfolder-info

When gnome-panel is restarted (via logout/login or kill) the user will be able to see the changes they have made to their menu.