I think people that experience this problem fall into one of two categories:
1. Intermittent failures that are typically solved by restarting,etc.
2. People that can not start a sync despite the simple tips in this thread.
I was in the latter category. Until I did a clean restore of the entire device, I couldnt sync. Then sometimes minutes, sometimes days later, I would again not be able to sync, and no simple remedies worked. Only anothe full restore would allow syncing again.
I think I finally figured out my issue. I was also having a problem with itunes match. A number of people have seen a similar issue where empty playlists get duplicated thousands of times. I had 67,000 emoty playlists. Turns out they were all synced up to icloud, so even after a restore (as above), they would come back. I finally got rid of the playlists by using a script that deleted them one at a time (took like 8 hours). If you have this problem, once the script finishes, be sure to allow itunes to run for a while to syn all the local deletes to icloud. I made the mistake of not waiting long enough, and 5000 came back. After subsequently removing them cleanly, I hae not had any problems syning. Certainly could see why 60,000+ playlists might cause the sync process to vomit.
After a month of this nonsense, I am finally free of the playlists and syncing reliably.