Boa tarde,
Esses colegas de trabalho... hahaha.
Olha, primeiro de tudo, isso não é tão impossível de ocorrer não. Alguns complementos adicionam publicidade nas páginas, mudam a página inicial e o motor de busca e até coletam dados do usuário sem o consentimento, tudo para gerar receita para o desenvolvedor. Por isso, é sempre importante não instalar qualquer coisa em busca de uma funcionalidade extra mas que muitas vezes é supérflua.
Mas no seu caso em especifico, fazendo uma busca rápida aqui e sem me aprofundar (estou em um celular com plano de dados limitado), parece que o problema está relacionado ao servidor DNS usado. Você sabe informar ser ele foi alterado recentemente (mais ou menos quando o problema começou)? Tente alterar o servidor DNS usado no computador e, se usar roteador, altere nele, para ver se o problema é resolvido.
Se não resolver, você pode tentar iniciar o Ubuntu por um DVD ou pendrive para ver se o problema persiste ou ainda, instalar um outro navegador provisoriamente, apenas para ver se o problema está mesmo no Firefox. Em caso positivo, talvez seja necessário apagar o perfil do usuário no Firefox para eliminar qualquer modificação que esteja causando isso. Isso elimina os cookies, histórico e favoritos, então, use com cuidado. Pesquise como remover o perfil do usuário do Firefox, pois ele não é removido apenas desinstalando e instalando o Firefox novamente.
Espero ter ajudado!