I've been noticing this for awhile under iOS7, but had been hoping it was a storage bug that would have been fixed in iOS8. Nope.
I "cheaped out" by only springing for the 16GB iPhone5, which means that I effectively get 12GB of space for stuff like apps, music, photos, etc… Shouldn't be a problem, but I've been hitting the cap pretty regularly now. I've resorted to deleting big apps, deleting all of the music that I'd put on the phone (thankfully the train ride is very short now), but still the danged phone reports no free storage.
Looking at the General > Usage reports, it looked like I was chewing up a couple of gigs just for photos. After grabbing then from my iCloud photostream, they're all in Aperture anyway, so I figured I'd just turn off Photostream temporarily to flush stuff out. After deleting all local photos manually, and then deleting the "recently deleted" items, I still get:
(3GB of the free space came from nuking the music I'd downloaded onto the phone)
Tethering the phone by USB and firing up Image Capture, it reports the iPhone completely empty of photos/video.
834 MB used for something, somewhere. But I can't seem to find it, and I can't seem to free it up. That's about 7% of the storage space eaten up by mystery ghost media files. Hopefully there's a way to force-nuke these mystery files so I have enough room for music on my phone (as well as room for software updates without having to delete stuff first).
Looks like when I eventually upgrade my phone, I'll have to spring for the extra cash to have more than 16GB (well, 12GB) available. The Cloudâ„¢ was supposed to make onboard storage less critical, no? Anyway. I'll keep trying to figure this out, and will post an update if I ever manage to clear up the phantom space…
UPDATE: @poploser recommended PhoneClean. I ran it, and it freed up over a gig of space (awesome!) but didn't seem to do anything about the phantom media files. Progress, though…