https://launchpad.net/~gnomenu-team/+archive/ppaTenta
#Adiciona o PPA
sudo add-apt-repository ppa:gnomenu-team/ppa
#Atualiza lista de repositórios
sudo apt-get update
#Instala o gnomenu
sudo apt-get install gnomenu
Esse que você baixou funciona no lucid, só que você deve ter esquecido de instalar alguma dependência, isso é, se você está seguindo os passos certos.
Mas é claro que também pode existir um bug/incompatibilidade.
OBS: Não uso isso.