MP3 tags in Hebrew show up in gibberish on my phone
It seems that the problem was the encoding that Windows Media Player used.  It uses the Windows Hebrew code-page (1255).  I used foobar2000 with the Chacon plugin to change it to the Mac Hebrew code-page (10005) which seems to be supported by my phone.