Siembre me ha sido incómodo que al navegar con nautilus no pudiera abrir un terminal directamente en el directorio. Sin embargo, es bastante fácil hacer un script que lo consiga.

Simplemente tienes que crear un script en el directorio ~/.gnome2/nautilus-scripts/. Al script lo puedes llamar como quieras, pero asegúrate que tiene permisos de ejecución. El texto debería de ser el siguiente:

        #!/bin/bash
        cd $NAUTILUS_SCRIPT_SELECTED_FILE_PATHS
        gnome-terminal 

Y eso es todo. La próxima vez que abras un directorio con el botón derecho deberá aparecer un elemento Scripts donde estará el nombre de tu script.

Si quieres conseguir más scripts para Nautilus, hay una página que contie multitud: http://g-scripts.sourceforge.net/