I'm confirming this because multiple people upstream have confirmed the same issue.
The upstream bug at https://bugzilla.mozilla.org/show_bug.cgi?id=242207 has 50 votes, and has been open for two years. If it's okay, I won't add another comment to the already long thread, as it won't make fixing the bug any faster.
The probable way that this will be fixed is through the implementation of a new history/bookmark backend: in the release notes for the first alpha release of FireFox 2.0, a new feature was:
New data storage layer for bookmarks and history (using SQLlite)
I would expect that when Ubuntu moves to FF2.0, this bug will be fixed.