I tried syncing bookmarks on my iMac running OS X 10.8, and you are right — iCloud is not syncing Safari bookmarks on my iPhone. I figured out how to fix this:
Solution: Unchecking and rechecking bookmarks option did the trick. Follow this step by step guide:
Launch System Preference, go to iCloud.
Make sure your Safari browser is closed. If not, quit Safari right now.
In iCloud, uncheck “Bookmarks.”
Check Bookmarks again. You will be asked if you want to “Merge” bookmarks. Go ahead and merge them.
Close System Preference. Launch Safari on your Mac. All your hidden bookmarks should be visible and synced properly through iCloud.