OK, I searched for an answer, and got some usable solutions, but none of them worked in my case.
Then, after trying to delete voicememos, playlists, unchecking music, movies ect. I still got the Error 13019 message. But now all my music on the iPhone was ghosted, but it still took up the memory on the phone. And I couldn't sync it back. So then I came to think that I could try sync it from another computer. And after syncing an empty iTunes music db, and then syncing on the normal computer (MacMini) it worked just fine.