"Other" data is real data that you put on your phone by using the built in apps. It is not music, not videos, not pictures and not App Store app data. It is "OTHER" meaning everything that does not fall into these categories. Such as:
- email messages and attachments
- Reminders
- Calendar entries
- Contacts
- Text messages
- MMS messages and attachments
- Genius data
- Music cover art
- Operating system settings
- Safari cache
- 3rd party Application caches
- bookmarks
- Game Center status
- Music catalog
Probably a few I've missed. There was a problem in an earlier version where deleted MMS messages left behind their attachments, but that has been fixed as of 6.1. The reason that deleting music recovers some Other space is because it delete cover art. But is also screws up your music, which will no longer play correctly.
You will find posts from people who said they recovered over 1 GB of space by just deleting old text messages.
If you want Other to be smaller you will have to keep less data on your phone; delete old MMS and texts, delete old email (especially from the "deleted" folder), clear the cache, eliminate cover art.