I've been having the same problem since the update but I just realised something and it fixed everything. I looked in my iTunes music library and some of my songs/albums had the "!" next to them.. they had somehow become unlinked. iTunes couldn't locate them.. they happened to be the same albums and artists that I was trying to sync to my iPhone 4s. I took the long route (just to be safe, you could probably just re-locate the files for iTunes but I didn't try it that way)
1. Delete your entire iTunes Library
2. Sync your phone and make sure there is now zero content in your iPhone library.
3. Re-Import your entire iTunes Library
4. Now iTunes properly locates ALL of the songs in your library.
5. Select your Albums, Artists, and Songs as you normally would and sync.
I know this won't work for everyone, but like I said, this issue sprang up for me right after the iOS 7 update and have tried every fix on this thread and others.