1-й раз через Synaptic - выбрал "полностью удалить",
2-й раз посредством :
su -
apt-get remove Firefox brasero
P.S. при повторной установке, попробывал также удалить open office - все нормально, ссылки из меню пропали, но Firefox и brasero остались по-прежнему.