Sim: como você suspeitava, o BleachBit mostra a seção do Firefox somente se os arquivos de configuração do Firefox existirem no seu sistema, para que você possa executar esse comando para excluir o perfil do usuário do Firefox
rm -rf ~/.mozilla/firefox
Depois, você pode excluir o cache do Firefox usando o BleachBit. Versões recentes do Firefox têm em outra árvore de diretórios.
Como Soren A apontou, remover um pacote normalmente usando o APT não remove seus arquivos de configuração.