After a reset and restore suggested by Apple's support for a completely different problem with my iPhone half of my music library become unplayable with the tracks appearing in gray and tapping them returning an error message "Object not available. This item can't be played".
This is how I solved it.
I first disabled music syncing for this device in iTunes to start over completely but interestingly enough, the tracks and playlists were not removed. I then manually deleted all playlists in the Music app and synced again (music sync was still disabled). This removed the playlists from iTunes (make a backup of your .itl-file before doing this if you follow these instructions) but left the non-playing tracks on the phone. After this I restarted the phone, but it didn't change anything.
Finally I changed the language (!) of the phone (because I wanted the error messages in English for this post) and lo-and-behold, suddenly the Music app was empty (except for the stupid U2-album Apple shoved down our throats some years ago). I then enabled music sync in iTunes again and suddenly it all synced as expected with all tracks playable.
If someone follows these instructions, I would suggest that you
- Disable music sync in iTunes
- Disconnects the phone
- Change the language
- Open the app selector and kill Music app
- Launch Music app again
Please let us know if this solved the problem.