Eu tive uma situação semelhante recentemente, onde o software-center não desinstalava alguns programas. Eu recomendo usar a primeira resposta primeiro. desinstalar aplicativos do centro de software via bash
Mas se isso não funcionar e o programa não estiver registrado no apt-get, você poderá remover os arquivos diretamente:
sudo rm -rf /usr/lib/<yourProgram>/
sudo rm /usr/bin/<yourProgram>
(Eu recomendo procurar nas pastas primeiro porque os nomes podem ser ligeiramente diferentes do nome do programa.)