I've got in the database several japanese/chinese/korean song that are shown with "random" characters (I think I should install a language package... but I don't know which one).
I got this problem too.
I usually use EasyTAG to fix my mp3 file info. But some of my korean songs were shown with "random" characters. I try to fix it several times in EasyTAG, but it didn't work (copy paste from google's results).
Finally, I have fixed this. You can directly change it from Rhythmbox.
Right click the song > Properties.
You can edit the field like title, artist, and more. Of Course with compatible encoding. And it works.
If I understand the question correctly, you have correct representation of Japanese, Chinese, and Korean characters in your song database, but these are not being rendered appropriately in the display. In this case, the most likely cause is missing font support. To install the preferred fonts for these environments, install the following packages:
If you happen to be running Ubuntu 8.04, the name of the packages for the Chinese fonts is different (I can't seem to find it just now). These packages do not appear to be available for oneiric: I believe this functionality is being integrated with the language-support tool, and do not know precisely how it will be represented when 11.10 is released.