I don't suppose you have a back up of your bookmarks? If not you could try importing these as "favorites" (as MS call them) into IE - "File">>"Import / Export". If this works you should be able to import them back to Firefox when you get it sorted.
Quite often removing something with "Add or Remove Programmes" leaves many configuration settings behind anyway so it might not delete them. It would also be worth looking at the Mozilla site to see if there are any other suggestions, or even posting a request.
There is an "Add on" called "Moz Back-up" to easily make back-up folders, I know it's a bit late now!
Good luck.