Acontece que a solução foi executar sudo dpkg-reconfigure ca-certificates . Não sei por que isso foi necessário, mas consertava as coisas para mim.
EDITAR
Como é um pouco relacionado, havia outra correção necessária para o Java encontrado aqui .