Ok, here is one for you.
When on the road I decided to take some time an re-org my book marks on the iphone.
So when returning to my computer and happy with the organization of the bookmarks I decided to sync them back to my laptop.

Now knowing how sync programs worked in he past for me I also decided to just clear the bookmarks out of the browser and then sync to have them all come from the phone to the laptop. After all there are some I didnt want to come back to the phone since I deleted so many I didnt use anymore.

So I did the sync and to my surprise the folder came over to safari on the laptop but no bookmarks. Ok, not a problem since its still on the phone, WRONG.
The phone also contained empty folders.

So I call apple and get passed up three levels. After the nice rep put me on hold to research this I though of an idea. I can force the phone into restore mode and hope the backup from last week had my bookmarks, the wont be he one I rearranged but at least I would get them all back. So I ran this idea by with the rep on the phone and he said it might work, but was not sure. He could not even confirm if the backup contained any bookmark information. He asked me to call back in with the case number because he was also curious about this being a solution.

Well I can tell you the backup contains a lot, including you browser history.
So this did work. But when I went to sync it again I lost them all.
Hmm, so lets upgrade the browser, maybe an issue with that, nope same results. So onto my third or fourth restore and then, I had a phone that could not be activated because ATT was down for system maintenance? 12 hours before I can get my phone activated. Sorry, thats another issue.

So I now make sure iTunes does not sync the bookmarks in hopes that this issue will be fixed with iTunes.

So am I correct to assume the sync does not go from the iPhone to the browser cleanly? But the phone will let you create new folders, rename bookmarks, and move them to other folder but you can not get this back to your computer cleanly with out possibly loosing all the bookmarks?

I suggest you dont try to rearrange the bookmarks on the phone for now.

Note: I was running iTunes 7.3.1
Activated Phone with ATT
Running OSX, safari bookmarks