I've had this problem since the shift from MobileMe to iCloud.
I had around 20.000 duplicates and I tried countless times to follow one tutorial after another with no luck.
To day I decided should be the day I came clean of these duplicates.
I tried the tutorial from Peter Berglund once more a few times without luck.
Searching the web from different ways to do this, I came across a programs called "BookMacster".
I though I'd give it a try.
What I did was keeping iCloud safari sync turned off on all my idevices. (2 iPhones and a iPad mini). But turned on, on my iMac.
On my iMac I ran BookMacster. It's pretty straight forward. Manually select all the duplicates and delete them.
The programs seems to stall on the computer, but just give it some time and it will come around.
After this, I used the Export setting in the program, to kinda export what changes I made to my bookmarks (delete the duplicates).
The I just watched as it synced with the bookmarks in safari.
I gave it like 45 min to make sure everything was synced to iCloud.
Then I turned back iCloud sync on all devices. After a while I checked my iPhone, only to get really frustrated. All the duplicates had synced back on. I checked the bookmarks on my iMac, and they still looked as they should without duplicates.
I the decided to just wait it out. And that payed off.
Right now one my iPhone 5 still has the duplicates, so I imagine that it's just a matter of time before that also syncs.
If this fails tomorrow, I'll check back here. But for now, this seems to have fixed my problem running for almost 2 years now... As you can imagine, I'm a happy camper :)