I have had this issue off and on and I think I finally found a solution (iPhone 6 - 64GB iOS 8.0.2, MBP 15" 2011, iTunes 11.4).
I have tried everything from un-syncing/re-syncing music, restoring my iPhone, setting my iPhone up as a new iPhone, reinstalling iTunes, and rebuilding my iTunes library.
I would get mixed results with these methods but I noticed that I would never have any sort of syncing issue (hanging on "waiting for changes," syncing artwork bug, music greyed out with red downloading circle in the music app, etc.) whenever I had less than 32GB of data synced to my phone.
Everytime that I would sync more than 32GB worth of data to my iPhone, issues such as songs not being synced and previously synced tracks disappearing started to come back up.
Take these steps:
1. Delete music from iPhone
- un-sync in iTunes
- or delete them from Settings->General->Usage->Storage
2. Sync music (Only selected songs and playlists unless entire library is < 32GB)
3. Test by rearranging playlist/syncing new songs to confirm no issues still exist
I doubt this may solve everyone's problem but it helped me so I figured I help anyone in search of a solution. I know how frustrating this can be. Obviously, in my case, it leaves me out of having 32GB of storage that I needed in the first place which is a hard setback.
I think maybe it has something to do with effective address calculations for storage? I don't know, just throwing ideas around. Hopefully a full fix for this sometime soon.