Yeah, the only way to reclaim the "other" space is to restore the device as new, and then restore the data from backup. If you use iTunes Match a lot, any downloads that do not complete all the way will occupy storage space until you restore the device. I learned that with iTunes Match active, downloading playlists and songs should be done in smaller chunks at a time. If anything stalls, then a lot of garbage data will remain behind. Deleting the music files from the settings won't purge this data.
Just as a maintenance routine, I restore my device as new about once every other month, or whenever there's a major interval iOS update.