Permalinks in language other thatn english

I am working on a website in hebrew and i want even the urls to be in hebrew. But the Permalinks in language other than english dont work.

I am geting 404 error for each non english slugs. i am not sure if it has to do with the following wp-config settings…
wp-confing.php details :

• define(‘DB_CHARSET’, ‘utf8’);
• define(‘DB_COLLATE’, ‘utf8_bin’);
• define (‘WPLANG’, ‘he_IL’);