I had a similar issue happen to me last week. I originally had about 300mb of 'Other' on my phone, and my music was set to 128kbps, I then unchecked the Convert button to have my music be higher quality, and boom, I had almost 2 gigs of other.
So I then did a complete restore (from a back-up) and I re-synced all my media back on and this time, I was back to my original 300mb of other, and all my game/app data was still the same (didn't loose anything).