I'm in the same boat and not really sure what's going on.
Of note, it looks like the current version of iTunes/iOS handles bookmarks differently than previous iterations:
"Your bookmarks are being synced with your iPhone over the air from iCloud. Over-the-air sync settings can be changed on your iPhone".
But uhhh, what's the mechanism for sending this info from my computer if I'm only running Snow Leopard (not Lion)? I do have iCloud bookmark syncing enabled on my phone, so I'm puzzled.
When I unchecked 'Bookmarks' under the iCloud preferences on my phone the check box for syncing bookmarks in iTunes returned.
Order is restored to the galaxy.