I have this problem when the Firefox has released it's Version 4.0.. but never thought about it much.. Some times instead of deleting the cookies from the remove history option, I set the firefox in a way that it deletes all the cookies and temp files after I close the firefox.. My setup is like this. I choose "Firefox will : Use Custom settings for history". Here, I only check "Accept cookies from sites" and it's sub "Accept third-party cookies" and change the drop down of "Keep Until : I close Firefox". and last check "Clear history when Firefox closes" - I apply the settings and I close the firefox, all the data will be gone (as I wanted..)

Now when I reopen the Firefox and want to make the setting of "Firefox will : Remember history" and click OK, it won't go to that option.. It instead takes me back to my last configured settings and will stay there. I have to uninstall the Firefox (during uninstall, I have to check the option of removing the personal data, else the problem will be back after installing firefox), and reinstall..