One Possible Solution
I have had the same problems as described by previous users on this thread. My "Music" category occupied close to 5 GB and my App category occupied less than 200 MB, while my "Other" category took about another 6 GB, leaving me less than 3 GB of free space on my 16 GB iPhone 3G running 2.1 firmware version. I have never jail-broken my phone or done anything out of the ordinary. Yet, I do have close to 90 app's installed. Obviously, because I was running out of space very fast due to this "Other" category, I searched forums and threads throughout the net and saw a few discussions about people resetting their phone entirely, albeit they had mixed positive and negative results, so I decided to try it out anyway. Before listing these steps, I also want to note I have not found any reason anywhere on the net why this "Other" category would occupy so much space. People were talking about album art and related data with song tracks, but album art alone will never exceed 1 GB, let alone reach 5 GB. From what I can guess, something else is definitely left over in your phone, perhaps when you install apps or when you upgrade your firmware, or this could be a major flaw or bug in Apple's software, which may be fixed in a future release. If you have a better explanation, please fill us in. Anyway, here are the steps I followed to recover more than 6 GB on my iPhone:
1) Back up all the data on your iPhone by right-clicking on the left menu on your iPhone tab in iTunes and selecting "Backup". If you frequently back up your phone, this process should not take long.
2) On your iPhone, go to Settings -> General -> Reset -> Erase All Content and Settings. Your phone will warn you this process will take more than 2 hours to complete, so try it when you have this much time available for this process. Also, I would leave your phone disconnected from your computer. Upon selecting this option, your phone will warn you 2 times asking for your confirmation. After you confirm yes, your phone will begin the process of erasing all your data and resetting everything back to its factory default configuration. You will notice a progress bar with no numerical percentage indicator and no remaining or elapsed time indicator either, so don't start freaking out. This process is excruciatingly slow. It should take about 2 hours as they said.
3) After the last step has completed, your phone will automatically restart. Upon rebooting, it will ask you to connect it to iTunes so it can activate your service and you can at least call people with your phone. Go ahead and do this. On your menu screen, you should notice only the default apps installed and everything else is missing, including your other apps, contacts, settings, text messages, bookmarks, etc. Now, after activating your service, you should notice iTunes asking you whether to set this up as a new phone or restore the settings from a previous backup. Select "Restore from backup" from the drop-down menu. This process should not take longer than 30 minutes.
4) After the phone has been restored, now you will need to sync your phone to copy over all the app's, contacts, bookmarks, etc. Depending on how much stuff you had installed to begin with, this process might take about an hour.
5) After you have restored and synced your phone, all of your app's will be rearranged alphabetically. Although I cannot speak for other users, I prefer to arrange my app's left to right in order of most importance to least importance and based on category, so you will have to rearrange your app's if you had them arranged before.
6) Now, I do not know if other users will experience this problem, but I ran into this issue after completing all of the above steps. For some reason, my Visual Voicemail was no longer working. When I clicked on Voicemail, nothing would happen and I could not access my voice-mail. After a lot more searching on the net, I found an AT&T support number, which I called, and they were able to assist me and solve this issue in less than 30 minutes. Here is the number: 1-877-419-4500.
All in all, this whole process took me about 4 hours to finish. But in the end, I was able to recover close to 6 GB of space occupied by this unknown trash on my phone, whatever it may be. Now, my "Other" category occupies less than 250 MB, which is much more believable. If you do run into the same issue as I faced, the above steps are just one possible solution. Perhaps I am killing a fly with a cannon, but if you do know of a more efficient solution, please let us know. Good luck!!