Talvez este certificado seja um dos que estão aguardando o processo de aprovação da Mozilla ver Bug #438825.

Those who are anxious for these root certificates -- those who already trust them and who have no patience with the Mozilla process for scrutinizing certificate authorities -- can download and install the root certificates themselves. The links are at < http://www.mozilla.org/projects/security/certs/pending/#ICP-Brasil >.

Você pode tentar adicionar o certificado manualmente (artigo em Inglês).

Estou com o mesmo problema. Uso meu certificado digital para peticionar em processos judiciais no STF, STJ, TRF e demais tribunais. Antes da atualização tudo funcionava, depois parou de funcionar. Agora só funciona no Internet Explorer. E já adianto que meu certificado não é um dos que aguardam aprovação da Mozilla, pois funcionava até ontem. Além do mais todos os arquivos e cadeias estão em ordem.