Friend has an iPhone 6s, 64GB currently saying there is no storage available, even though there clearly should be. Also looked up & saw it isn't unique to him. Deleting things still result in an Available storage of 0 bytes.
Has happened again a couple of times. Couple of minutes again the storage was going down at an alarming rate, a GB or so a minute. A restart stopped it though & it is back to normal again. Difference being he is now running iOS 9.1 beta.
Ended up up finding out the cause. It was somehow related to iCloud Music Library.
I think what's happening is its trying to download my entire iCloud music library to my iPhone. And then when it runs out of space and realizes the library can't fit and I do a sync it deletes the library and I get back my space