Try switching to another persona. In order to switch to another persona that you had previously installed, do the following:
To uninstall the other ones you can click the Remove button on them and they'll be uninstalled instantly.
I fixed this by moving from FF17 to 18. Nothing else seemed to work. I had to go to the Firefox download site - the automated updater failed too. I think the problem was caused by a failed update.
Make sure that you do not run Firefox in (permanent) Private Browsing mode.
I also recently had this problem. I discovered that the issue was related to computer issues corrupting my most recent update from Firefox. Re-downloading Firefox 19 got rid of the problem.
In the Clear Recent History window, at the top, Make sure Time Range to Clear is set to Everything. After the update it must have set it to Last Hour Only automatically.