Thanks for the tip BUT please Apple techies this should not happen so fix it. In the UK we call it customer service, perhaps Mr Job's heirs should add that to their lexicon.
Please note that this is a user-to-user technical help forum hosted by Apple. We are all just users like yourself here. You aren't talking to Apple.
If you wish to give feedback to Apple use http://www.apple.com/feedback
I just had this same problem! but restart didn't help for some reason and I was digging for more than 2 hours!! then I restarted again (for another reason) and suddenly they appeared.
I don't trust storing them there anymore. i recommend everyone to store on some exterrnal cloud service that supports mobile devices.
You can try Diigo or Favsync. Diigo is not so good for mobile, but you can also save other content, but purely for bookmarks I would go with Favsync. You can even choose which bookmarks to show on mobile and which to show only on pc and there's some more stuff i need to discover there.
Hope it helps!