@Lyrositor, você já tentou o seguinte:
gconftool --set /desktop/gnome/interface/menus_has_icons --type bool true
gconftool --set /desktop/gnome/interface/buttons_have_icons --type bool true
Eu ficaria curioso em saber se isso ajuda a atenuar o problema com os ícones do menu.