This may be worth a new post, but just a couple of followups:
I've avoiding upgrading to 8.4 waiting to hear that this problem was fixed. Yesterday the problem was back-ported to 8.3.
Yesterday on 8.3 all of my playlists and songs suddenly disappeared. Same symptoms as everyone here has noted: space on the device was shown as used in "Other", but Apple Music only showed the few dozen songs I'd purchased through Apple, (and none showed as being on the device). When I connected to the desktop for backup, iTunes could see the music on the phone, but the phone couldn't.
Note, even upgrading iOS 9 and restarting did not fix the problem.
Like others here, the machine with the originally ripped CDs was not available to me, so just re-syncing was not an option. Luckily I had brought iExplorer from Macroplant after a previous iPhone upgrade to help me move my iPhone content from one iPhone to a new one. (Note: I'm not associated with the company other than having used it to save my iPhone data in the past).
What I ended up doing was using iExplorer to find the raw music files on the iPhone. The iExplorer default "copy my music" function didn't work (I guess it depends on the phone to identify the music?) but looking through the raw media files in the iExplorer browser I was eventually able to find thousands of obscurely named files on the phone (with names like XKL13xxe.mp3 that clearly contained music, organized into numbered folders of a couple of hundred files each). I used iExplorer to copy these files to a random directory on my desktop (this was on a PC, I assume it would work on Macs too). From there, I copied the files into iTunes via drag and drop (the metadata describing artist, album, etc. was maintained through this process).
After verifying that iTunes saw the same number of music files on the computer and on the iPhone, I then had to use iExplorer to manually delete all the audio files off of my iPhone, because even though I told iTunes to erase my music files off the phone (so I could resync from a new machine), it still couldn't recognize the music files to delete them (and so there wasn't enough room on the phone to copy new copies of the recovered music to the phone). After doing that deletion of music and resyncing from iTunes I finally got to a point where my music was restored. I still lost my playlists, though I suspect it may have been possible to save them if I knew how they were stored (I only had one playlist of "favorites", so that wasn't as big a loss for me as it is for others).
So I guess all in all this is (a) a warning that this can happen on iOS 8.3 also, and (b) an ad (indirectly) for the iExplorer product, though there may be other products that can perform similar functions.
Good luck! This was extremely painful and infuriating. The fix was extremely non-obvious, even having read all of the suggestions in these posts.(In fact, most suggestions weren't available, given that I was on iOS 8.3, so many of the settings options didn't even exist at the time.)
