Comment 15 for bug 130055

@BrianK: nautilus-script-audio-convert is not a "nautilus script" in the strict sense: it is something more advanced and complicated from a developer point of view, which indeed integrates in the main nautilus menu.
(notice nautilus scripts in the strict sense aren't "just old technology": I like the idea to have possibly dozens of them in the "scripts" submenu, not cluttering the main nautilus menu)

You may want to install package "nautilus-actions" and then run System->Preferences-> Nautilus actions (or something similar)