I had a problem. until just now. with my playlists not syncing, and my solution may work for some of you. I did not have the "Waiting for changes to be applied" issue (thank goodness). I don't think I had any missing songs, either. Just songs missing from playlists.
How I identified which songs were missing from my playlists: In iTunes (mine is the Windows version) Playlists, sort each troubled Playlist by a column of your choice, like Name. Then right-click on the playlist name on the left and select Copy To Play Order. Sync to your device(s). Now your playlists in both iTunes and on your devices will have the songs in the same order, making it easy to compare. You do lose your original play order, but I always use shuffle anyway.
In this manner I discovered that song names with parentheses in the name seem to be my entire problem -- they were the songs that were missing from my playlists on my devices. It also seems that a song with a parenthesis can affect the next song in your playlist. This is not good, because all or nearly all these songs were purchased from the iTunes Store, and the song names, as purchased, can have parentheses.
To fix, rename the song names, and then re-sync. It is unfortunate to lose your original song names. All the more so that when (I assume) Apple fixes this issue, you shouldn't need your songs renamed any longer. So as to not lose the parenthetical information from your song name, I suggest replacing the first parentheses with a hyphen and a space, and not deleting the words. Word of caution: I don't know if there are any unintended consequences of changing your purchased song names.
One way to find straggler songs that still have parentheses: In iTunes, go to Songs. Upper right, in the Search Library box, type a left parenthesis. The resulting list is broken down by Artists, Albums, etc. Find Songs, and hit the Show (all) text. This will show the songs with parentheses, although I don't think it allows you to rename the songs from here.
I have so many songs with parentheses, that I'm giving up for tonight. So, I still have the problem, but, no longer do I have it with with the songs I've renamed.
Windows iTunes 11.1.5.5 iPad and iPhone 5 with 7.0.6