Server Settings
OS: Linux
HTTP Server: Apache2
Database: MySQL (utf-8)
Scripting Language: php 5
Software: wordpress 3.0.4 – wp-confing.php

define('DB_CHARSET', 'utf8');

Create an .htaccess file in your root directory ( e.g www.example.com/ )

vi .htaccess #(you may have to sudo or su)

Add the following lines in the file .htaccess file…

# Disable Directory Browsing
Options All -Indexes
# Secure access to .htaccess files
<Files .htaccess>
order allow,deny
deny from all
</Files>

Save the file and exit vi (:wq).
You may have to give full access rights to .htaccess!?

chmod 777 .htaccess #(you may have to sudo or su)

Open your favorite browser, go to your www.example.com/wp-admin section then choose

Settings -> Permalinks

and apply your custom structure…

( e.g /%year%/%monthnum%/%postname%/ )

Save Changes

IMPORTANT
Remove the full access rights from .htaccess!

chmod 644 .htaccess #(you may have to sudo or su)

You are done! Enjoy your wordpress custom permalinks in your preffered language.

I have test it with greek, russian and arabic and worked as a charm!
See an example…
http://www.my-soul.net/blog/