O Ubuntu tem dessas coisas esquisitas mesmo.
Por exemplo, eu havia instalado o xmms, mas não gostei e desinstalei depois.
Um dia, fuçando no terminal, digito xmms e - voilá - o bendito abre na minha frente !?!?!?!
Fui no sinaptic, ele não estava instalado, dei um apt-get remove no terminal e ele me retorna a mensagem
''o xmms não está instalado, portanto não será removido''
Ou seja, tenho um programa 'fantasma' no meu sistema hehe