Я не раз замечал, что при установке новых программ в скрипте говорится, что будет перестраиваться меню, вот что нашёл по памяти:
/etc/menu
Пройдясь по ссылкам понял, что меню хранится где-то в домашнем каталоге пользователя.
Но вот незадача, для сеанса xfce 4.8 меню будет работать, а для xubuntu - session не будет, ибо там своё меню.
Вот ещё если захочется править меню вручную:
/etc/xdg/xdg-xubuntu/menus/xfce-applications.menu
/etc/xdg/menus
Только опять для сеанса xfce4.8