This will allow you to open a Terminal instance in context in Nautilus.
sudo aptitude install nautilus-open-terminal
You will need to restart Gnome for it to take effect. Note that all you user programs will be terminated...so save data first. Then either use
sudo /etc/init.d/gdm restart
And Bob's your uncle. Now you can right-click and open a Terminal.
