The problem might be the terminal: the fact that it's dealing with right-to-left correctly makes it seem that the terminal just can't display the hebrew characters. If you're using one of the kernel tty's, you might try starting X and using xterm.
Although I mount in Konsole, the problem is evident while browsing the file system in Konqueror, which supports Hebrew on the local system (and remote systems via ssh) perfectly.
I guess that's not it then. I'm afraid I don't have any other ideas. Christopher