Although a lot of people claim it is not possible yet for GNU/Linux to understand characters other than ASCII, I've found that it can concerning user names - using the useradd command (not adduser).
The actual problem seems to be a standard the unix commands have to follow:
http://www.opengroup.org/onlinepubs/009695399/basedefs/xbd_chap03.html
But it looks like the useradd accepts arbitrary usernames, which is cool! So I've tried my name in Greek:
sudo useradd -m Σάββας
Then adding a password:
sudo passwd Σάββας
And that is all that is required!! Maybe some programs aren't ready yet, but so far I've tried: terminal, console, firefox, rhythmbox, totem player. None of them returned any errors nor did they crash.