Hi there!

I have the same issue for a few weeks now. I sync two Macs with Lion and my iPhone 4 with iOS 5.1. All devices have turned bookmark sync on, and of course I am using Safari on both devices (would be stupid if not!).

The problem seems to be to pull new bookmarks from iCloud, not the sync towards iCloud: When I add a new bookmark on Mac 1, Mac 2 and the iPhone do not get the bookmark. When I switch off sync and then switch it on again on Mac 2 or iPhone the new bookmark appears. Instead of toggling bookmark sync on the iPhone it helps to add a bookmark on the iPhone. The bookmark added on Mac 1 will appear on the iPhone.