Isso acontecia comigo, tal como se vê no tópico:

• Ícones duplicados no gnome-shell

Após alguma procura, encontrei a solução aqui:

• http://forums.linuxmint.com - Mint 12 Tips & Tricks Guide (updated Jan 10)

Basicamente, o texto acima informa que a instalação do Mate (desktop alternativo, estilo GNOME 2) causa a duplicidade, que pode ser eliminada de duas maneiras, uma simples, outra nem tanto.

A simples, que funcionou para mim, consiste na remoção do pacote "menu-xdg" e dos órfãos "criados" (ou talvez já existentes, não sei ao certo), comandando:

sudo apt-get remove menu-xdg
sudo apt-get autoremove

Após, você deve encerrar a sessão e logar-se novamente, verificando se o problema foi resolvido.

A complicada seria instalar o "alacarte" (editor de menu) e remover "na mão" as entradas duplicadas. E para tanto:

sudo apt-get install alacarte

Abra-o em "main menu" (pelo terminal, use o comando "alacarte", sem as aspas) e desabilite o menu "Debian" (principal fonte dos ícones duplicados) e o que mais você quiser.

Espero que esta dica funcione também para você.

Até a próxima.