Era successo anche a me perchè il file che conteneva i segnalibri era stato sovrascritto da un file bookmarks vuoto.
I segnalibri di Firefox sono contenuti in un file in questa cartella:
C:\Documents and Settings\[TUO PROFILO]\Dati applicazioni\Mozilla\Firefox\Profiles\[NOME STRAMBO].default
In questa cartella troverai un file chiamato bookmarks.html
Vedi se esiste questo file e se contiene qualcosa...altrimenti, mi sa proprio che li hai persi...
Scarica mozilla backup e prima di fare qualsiasi aggiornamento usalo per salvare tutte le configurazioni di FF così se succede qualcosa puoi usare quello per ripristianare il tutto.