Tudo bem, descobri como resolver o problema, embora não exatamente "por que" isso aconteceu.
Parece que eu instalei uma versão independente do Firefox (provavelmente uma versão Mozilla, do mozilla.org). Depois de um tempo, a versão suportada pelo Ubuntu chegou ao computador, não tendo certeza se durante uma das atualizações do SO.
Então, quando eu corri o Firefox, eu estava executando a versão instalada na minha pasta pessoal (que tinha atualizado para 11, a versão atual neste momento), que por algum motivo teve problemas para exibir o ícone. (ao executar esta versão a partir de um terminal, há um monte de mensagens de erro do gtk).
Quando eu corri o Firefox a partir da linha de comando, a versão que rodava era a versão do Ubuntu Mozilla Team. Esta versão conseguiu exibir o ícone, apesar da mensagem de erro (que agora acredito não estar relacionada). Ambos o Firefox usou os mesmos dados de perfil, daí a confusão.
Portanto, a solução é apenas usar a versão correta. Embora ainda não saiba exatamente porque a versão do moz tinha problemas com ícones.