if you have the google toolbar for firefox, make sure you have the google start page turned off. It caches its thumbnails to the same database file as your bookmarks and history, and the bigger that file gets the more problems you will have.
I stopped having problems in both Windows and Ubuntu after disabling the start page in the toolbar settings and deleting the bookmarks database (places.sqlite) and restoring my bookmarks from backup. (I also reclaimed over a gig of space on Windows by doing that)