I have never been able to sync all my music in one try. Usually it takes me 3 or 4 syncs for everything to finally load. Same with apps.
Now each time I get a new phone I don't change anything, just sync. When it's done I just go about my day with whatever transferred, then sync again later or another day. Eventually everything transfers.
Wish I had a less frustrating answer, but at least it (eventually) works for me.