It seems that when someone uploads a file with Hebrew characters to my server, when people download it with Chrome, or Firefox, they seem to download the exact file with the same Hebrew filename. The problem occures when they use IE. They see the filename in Gibberish. Even I see in Gibberish with IE, even though I'm using a Hebrew operating system.
A quick Google search (thanks to my host), has brought up these results:
http://drupal.org/node/766392
http://blooberry.com/indexdot/html/topi ... coding.htm
It seems that this is a quite known problem.
Thanks for your help!