Another cool thing is that if the All Bookmarks menu was the last thing you were on, you can get back to it by pressing the Menu ring once (rather than holding down the Mark button).
The only workaround I can suggest (until they actually fix it) is to connect your Reader to your PC every couple of days. Kind of a pain I know, but if the feature is as important to you as it sounds like it is, it would preserve it.
