I segnalibri li avresti dovuto salvare prima di formattare, o cmq salvare la cartella Firefox che sta in C:\Documents and Settings\[tuo account]\Dati applicazioni\Mozilla\Firefox\Profiles...
Lì ci stanno i Bookmarks aggiornati automaticamente in formato html.