Você instalou usando o dpkg? Pergunto isto porque diz que usou um .deb que "conseguiu por ai".
Caso tenha sido assim, use o próprio comando para remover o programa, e lendo o seu help (através do comando man dpkg) basta dar um dpkg -r
É que não lembro se foi pelo deb(e nesse caso com certeza apenas dei um duplo clique nele, sem comando nenhum ele se instalou) ou se foi pelo script que disponibilizaram em um tópico aqui do fórum.
De qualquer modo tentei o dpkg. Olha o resultado:
arilson@possante:~$ sudo dpkg -r thunderbird
Password:
dpkg - aviso: ignorando pedido para remover thunderbird que não está instalado.
AuhaUHAUHUhAU falei que ele é teimoso?!!