Okay people.... after HOURS and HOURS of trying to figure this out, here is what worked for me.
- I followed people's advice to go into General > Settings > Usage and found music and deleted all the music
- Then I also connected phone to iTunes via USB and clicked "sync music" off and then synced so now my phone had no music
- I synced and backed up phone with no music
- Then I re-synced music and EVERYTHING WORKED GREAT!!
BUT>>>> then if I came and hooked in my phone again, it would backup, and then it would go through this "Syncing Artwork" step and after that was finished it would start deleting all my music again. If I played it on my iPhone it would just shuffle through until it found a MP3 that I purchased from iTunes and it would not play any ripped CD MP3s or MP3s bought elsewhere but still in iTunes.
So what I did (and wish I had done instead of doing steps #1-4 above) was to find the "Album Artwork" Cache folders and DELETE THEM ALL! For me, they were located in C:\Users\UserName\Music\iTunes\Album Artwork. Delete all folders EXCEPT DO NOT DELETE "Download" folder or "Cloud Purchases" folder. iTunes can repopulate the cache folder from the cover art embedded in your MP3s, but for some reason it cannot do that for the iTunes downloaded MP3s, because those are not embedded into the MP3 file, but are in this folder.
Once I deleted the "Cache" and other folders (except for the two I mentioned above), I just resynced my phone and all the music that was on my phone (but would not let me play because it would spin through the music and then delete it off my phone) just started working again!!!!
OBVIOUSLY this is a temporary fix only, and you may have to delete these folders, sync, and then just pray it works. Worked for me. Not syncing my phone for a while because it is working.