I found out today that if you’ve installed a script in Nautilus, you won’t see it in the contextual menu until you’ve visited the script directory in Nautilus.
Install a script in ~/.gnome2/nautilus-scripts/ and making it executable.
Then visit that directory in Nautilus to “enable” it.
I’m not sure if you have to do this for every script you install, or only for the first one.