Sheesh. I finally upgraded to the phone 4 from my 3g due to all the performances issues on the 3g that were introduced by software "upgrades", and within two weeks I lose hours and hours due to Error 13019 sync errors.
I tried everything listed at
http://support.apple.com/kb/TS2830 to no avail and finally called Apple Support to make an appointment. Before they called me back I resorted to a full reset/restore of my phone, and synched repeatedly, each time adding something else I had previously unchecked (per the instructions at TS2830). All that seemed to work, and that's what I reported to Apple who confirmed that that's what they would have recommended. I expressed my concern that the problem seems to come back, but they said that should not happen in my case since I'm at iTunes 10.1.1 and iOS 4.2.1.
Of course, soon after I hung up I realized I had not synced my ring tones. So I checked "sync ring tones" and did another sync and got the error 13019 again. I also noticed that it was copying voice memos down to my iPhone even though the phone already had all of them.
So, finally, I deleted all my voice memos on the phone, and this time the sync worked. I'm appalled at how long this problem has been open and continues to plague countless customers.
By the way, I lost some app data when I restored my iPhone. For example, the Skype app no longer knew my Skype userid and the game apps started from scratch instead of from where I left off. Is that normal?