IF YOU DON'T WANT TO READ THE LONG STORY, HERE IT IS IN A NUTSHELL: Get "iFunBox" (or some other file management app) and look for any hidden files on your iPhone. Then DELETE them!
I have been having a the same/similar problem since updating to ios8 (whenever it was when it first came out) to my 4s. I kept getting messages that the storage was full when i knew **** well that it wasn't! Also the phone would say one amount was free, iTunes would say another amount… nothing ever matched up. When looking under "manage storage" on the phone, just flipping back and forth from each app's info to "storage" would make the "available" amount go down (not a lot, but it kept filling up!). Music would show up in the "on my device/music" that i never loaded or downloaded from my library. When i deleted them they always came back but showed up as zero k. This always started when i turned the phone on to show all my music and turned on the iCloud library. The only thing that seemed to clear all this extra storage was to reset it and restore from back-up. Very time consuming and ineffective as within a few days it would start with the storage full messages again. The other day i read someone had used an app on the mac called "iFunBox" to find hidden files in their phone and delete them. i downloaded the app (free!) and found that i had hidden files too. A LOT OF HIDDEN FILES! In the phone under the "Raw File System" i found a folder named "Cloud Assets" that contained a little over 440mb of mp3 & m4a files, and accompanying plist files. I don't keep any music on the phone anymore, i stream everything from iCloud. It seems these were made from music i had recently listened to. The names were all altered. I copied them to my iMac so I could open & inspect what they were. Their names looked liked this:
CloudAssets/persistentid-4023831224729247364-HQ.mp3
CloudAssets/persistentid-4023831224729247726-LWHQ.plist
CloudAssets/persistentid-4023831224729249236-LWHQ.m4a
There was no way to play them from the phone, so i deleted them all and freed up a lot of space. BUT… as soon as i began streaming music again, a whole new batch showed up. Deleted them. Streamed. More files! This has been going on for the last 3 days. So big question is WHY DOES IT KEEP DOWNLOADING/GENERATING THESE FILES! (Apple??? What is going on here)
PS- i have just found a lot of weird cache files of iTunes artwork. Over a 1.5GB's worth of album and video artwork that i can find no logical reason for being on the phone (as their is no corresponding music or video on the phone either). Gonna delete them too!
- iPhone 4S iOS8.4.1 (but most of this took place with earlier versions) capacity: 5.34GB