¿ Pero los sigues teniendo en el sistema ? ¿ has comprobado que estan, ejecutandolos desde la terminal o con alt+f2 ?

Si sigues teniéndolos y lo único que quieres es recuperar el menu de aplicaciones en el que si que aparecian:
Las entradas que tenemos en el Menú de Aplicaciones se guardan en el directorio /home/usuario/.config/menus ; en este directorio hay varios archivos:

- el archivo applications.menu: hace referencia a la última modificación del  Menú de Aplicaciones que hayamos hecho.

- otros archivos: applications.menu.undo-x ( siendo x un número que cuanto mayor sea hará referencia a una modificación del Menú de Aplicaciones mas cercana a la última que hayamos hecho )
Prueba por tanto a recuperar desde ahi el menú de aplicaciones que quieras.

------------------
El archivo  /etc/xdg/menus/applications.menu hace referencia al archivo original del Menú de Aplicaciones que teníamos nada mas instalar el sistema, antes de que empezáramos a configurarlo a nuestro gusto. Por lo tanto si nos hubieran desaparecido los archivos que hay en el directorio /home/usuario/.config/menus sin que hubiéramos hecho una copia de seguridad como se indica anteriormente, aún podríamos recuperar el Menú de Aplicaciones original, copiando el archivo /etc/xdg/menus/applications.menu al directorio/home/usuario/.config/menus  , recuperando así el Menú de Aplicaciones original, teniendo que volver luego a configurarlo a nuestro gusto.

/etc/xdg/menus/applications.menu   >>> home/usuario/.config/menus


Extraido de http://hatteras.wordpress.com/2008/10/09/copia-de-seguridadrecuperar-menu-aplicaciones/

Pues el porque sigo sin saberlo, lo he solucionado copiando los lanzadores desde otro PC con ubuntu, el file manager iba bien pero el ubuntu tweak no funcionaba porque ya no estaba instalado!!!!.
Lo he reinstalado desde los repositorios y todo ok, sigue siento un misterio el porqué de su desaparición súbita
Nota:
Tu avatar me sigue confundiendo.... se me hace difícil leer tus post's, un extraño ataque de estrabismo me suele afectar.

En ocasiones al actualizar pasan esas cosas, lo de que se desinstalan cosas.

Esas pijaditas hacen que los Windoneros le cojamos miedo al LinuX....

Pues hombre yo uso linux pero reconozco que raparo muchos windows que despues de actuliazar ni arranca el sistema, y eso es muy a menudo.

Apaga el pc cuando  se este actualizando un winbugs y luego lo pruebas con un linux y me cuentas, la diferencia es abismal

No llevara la sangre al río, al XP le tengo mucho cariño y ciertos programillas no los tengo localizados en LinuX y/o no me son tan flexibles o fáciles de usar.