To answer my own question, the solution can be found at...
http://linux.rasmil.dk/cms/modules/news/
Installing the nautilus-open-terminal package with yum and
restarting gnome brings back the "Open Terminal" menu. The
only downside is that it now is in the middle of the drop
down menu instead of on top as before.
Jack