Bookmarks not saved
This article deals with problems adding, deleting, and making changes to bookmarks. For bookmarks that were saved previously but are now gone, see lost bookmarks.
Changes lost on restart
This problem can be caused by a read-only bookmarks.html or bookmarks.html.moztmp file in the profile folder. Deleting or modifying bookmarks will also have no effect and the profile folder will fill up with multiple numbered bookmarks-n.html files. Removing the read-only attribute will again allow the bookmarks to be updated [1].
Add Bookmark dialog not working - Firefox
Corrupt localstore.rdf
A corrupt localstore.rdf file in your profile folder can cause this problem. To fix it, see this article.
Bookmark Duplicate Detector
The Bookmark Duplicate Detector extension may cause the Add Bookmark dialog to fail [2]. If updating the extension doesn't help you should uninstall it.