A veces al momento de desinstalar tal vez no marcaste alguna opción llamada "Borrar datos de usuario".
No me da esa opción al desinstalar , de hecho es que no me da ningún tipo de opcion
De todas maneras, revisa si tienes el nav. sincronizado con Firefox Sync (si es que lo usas, claro).
No se que es esto , pero voy a mirar a ver si lo encuentro
Thanks