Tente recuperar a partir de um backup automático:

• Restaurando backups
• Vá em Favoritos >> Exibir todos os favoritos (Ctrl+Shift+B) >> Importar e Backup >> Restaurar

Obrigado pela dica, Diego Victor.

Gostei de saber que o FF faz backup dos favoritos sozinho. Pode me ser bastante útil no futuro!

Mas, infelizmente, todos os backups que estavam disponíveis tinham conteúdo bem inferior aos Favoritos que eu tinha antes do problema.

Vou tentar na segunda-feira no FF do trabalho. Quem sabe lá os backups disponíveis estejam em melhores condições.

Ah, restaurei alguns backups bem anteriores à data da atualização e todas as restaurações foram incompletas e com quantidade de favoritos bem parecidas (ele mostrava uma lista com uns dez itens de datas). Agora só aparece uma única possibilidade de data. Acho que os backup foram se sobrepondo até que só restou a última versão. :-( Agora é que ferrou mesmo!

Consegui resolver o problema!!

Acessei um PC com o FF mais velhinho (com Versão 28.0, que não usa o novo sync), acessei o Sync utilizando minha conta+senha+chave, mesclei com os favoritos desse "novo" PC; Exportei os favoritos mesclados para um arquivo e importei esse arquivo no meu PC com problema.

Pronto! Voltei a ter meu favoritos novamente!