Do you use Google Bookmarks? Can you find your bookmarks at:
http://google.com/bookmarks ?

Also see: http://groups.google.com/group/Google_Web_Search_Help-Personalizing/browse_thread/thread/49e38c95a0d29343

I have mine, looks like it's affecting a portion of users.

I've mine too (in the web history, in the toolbar Google Bookmark button and in my Google unfilied Notebook). But I admit it can be very annoying... It seems that the Notebook keep them. Hopefully.

seems of on the toolbar – not checked web history