Problema resolvido.
No terminal, tentei (já havia tentado antes, na verdade), o que zeroday sugeriu. Não deu certo:
besourolaranja@ubuntustudio:~$ sudo apt-get install gnome-app-install
Lendo listas de pacotes... Pronto
Construindo árvore de dependências
Lendo informação de estado... Pronto
O pacote gnome-app-install não está disponível, mas é referenciado por outro pacote.
Isto pode significar que o pacote está faltando, ficou obsoleto ou
está disponível somente a partir de outra fonte
No entanto, os pacotes a seguir o substituem:
gnome-codec-install
E: O pacote gnome-app-install não tem candidato para instalação
besourolaranja@ubuntustudio:~$ sudo apt-get install gnome-codec-install
[sudo] password for besourolaranja:
Lendo listas de pacotes... Pronto
Construindo árvore de dependências
Lendo informação de estado... Pronto
gnome-codec-install já é a versão mais nova.
0 pacotes atualizados, 0 pacotes novos instalados, 0 a serem removidos e 352 não atualizados.
Obrigado pela resposta rápida, zeroday. Pelos meus parcos (parquísimos) conhecimentos, eu tinha o programa, mas não seu frontend, é isso?
bawlaw resolveu meu problema, baixei pelo synaptic. Meu problema com o synaptic é: eu não quero saber de quais pacotes vou precisar, quero fazer uma busca pelo nome de fantasia do programa e acha-lo...
Obrigado.