La ventaja de Gnome y en Linux en general es la capacidad para personalizar cada una de las opciones con sencillez.
Manos a la obra. Desde terminal:
gconftool-2 --type Boolean --set /desktop/gnome/interface/menus_have_icons True & killall gnome-panel
Si queremos dejarlo todo como estaba ejecutamos el siguiente comando:
gconftool-2 --type Boolean --set /desktop/gnome/interface/menus_have_icons False & killall gnome-panel
Otra opción es usando el editor de configuraciones de Gnome. Alt+F2 y ejecutamos gconf-editor. Seguimos la siguiente ruta: desktop > gnome > interface y seleccionamos "menus_have_icons".