This also was happening to me. Every time I was closing and restarting firefox i was losing also all my tabs. I notice the problem was that sessionstore.js was been deleted each time I closed firefox. In fact I had some old sessionstore-<#number#>.js in my profile but they were dating from further. I tried renaming one of those before opening firefox and in fact i got old tabs restored, but then again after closing firefox the sessionstore.js was deleted.
Finally I find out the reason is that at the same time I had ask firefox to restore my tabs in the Privacy Tab from the Preferences Window I set Firefox to clean up my History each time Firefox close. So what this setting was doing was to remove the sessionstore.js each time I was closing Firefox. The workaround was to enable Firefox to remember my History.
In fewer words. Try to do this:
Open Edit Menu > Preferences
Change to the Privacy Tab
Find the History part. There is a checkbox reading: "Clear history when Firefox closes". Make sure to uncheck that box.
Close the Preferences window, then Firefox and restart again.