I must admit, Apple support has actually been quite good concerning my ongoing problems with Apple Music. When I called Apple via the number on their web page, I received a call back from a real live person within 15 minutes. They quickly passed me up to the next tier as soon as I described the problem. The second person was unable to solve my problem, made some suggestions and asked me to email him back with the results. He called me back on Sunday, and made the Apple Store appointment for me. The person at the Apple Store could not solve the problem, and told me he would write something that gave me priority to the next tier of support. Each time they made an effort to "reflect" a feeling - "You must be very frustrated", "I know this is frustrating".
During each of these encounters, I received an email from Apple asking for feedback, which I was happy to give, including my dissatisfaction that the problem remained. During this process, they asked if I would be willing to receive a phone call about it, and I said yes.
Since last week, all my music disappeared from the Music app, several times I had been able to reinstall the music only for it to disappear again. This last time it took many tries to try and again download the music, but today I was able to get 4,700 songs back on my iPhone. But I'm waiting for them to disappear again.
This evening, I received a phone call from a senior tech at the local Apple Store. He was very knowledgeable, and some of his comments reflected he had seen my written feedback. We discussed the previous attempts and noted when I wiped the iPhone to the factory settings, I had restored the phone from my iTunes backup. I knew he was going to recommend wiping it again, and this time do a clean install, which in my case would be extremely time consuming. He did suggest wiping the iPhone again, suggesting either a clean install, or doing a restore from the iCloud backup vice the iTunes backup on my laptop. I knew the iTunes backup is a direct copy of what was on the iPhone, including software patches/updates from the original, which end up taking excess space on the iPhone and can possibly be corrupted. He then explained an iCloud backup/restore does a clean install of iOS to the latest version I had installed (not copying back the original plus patches which might be corrupted), and will restore everything back to the way I had my iPhone set up, including the wallpaper, etc. I will have to redo my fingerprint scans, and extra Credit Cards in Passbook as this is only stored locally on the iPhone.
I have so many apps, it was about to exceed the free iCloud storage space, so had excluded most of the apps in the iCloud backup that the iPhone does automatically everyday. So to make this painless, I purchased 20GB of iCloud storage, and have made an iCloud backup which includes all my apps.
Then Apple just released iOS 8.4.1 (which reportedly has many fixes to Apple Music but not the problem I've been having), so I installed this first, then backed it all up to iCloud, wiped the iPhone to factory new, and am now restoring from iCloud. This time it has already begun downloading music, which is a good sign. I'm hoping this solves the problem, since it was running fine until one week ago when all the songs went missing.
The same issues occurred to me, too. I'm running iOS 9 PB 3 and all my downloaded playlists are now greyed out, still the available memory did not increase. Just as you described. Disabling and enabling iCloud Music Library didn't change anything.
Seems like this issue occurs with Apple Music on iOS 9 and iOS 8.4.X...
I reported this to Apple with the iOS 9 Beta Feedback Assistant. Let's see, how this goes.