This is for everyone that has problems with Greek subtitles on their (Linux) system.

For Xine, gXine, Kaffeine etc. i did the following :
1 Get the source of xine-fontconv utility from the misc directory within the xine-lib sources from http://xinehq.de/
2 Compile it (in the shell "console") typing :
gcc xine-fontconv.c -o xine-fontconv `freetype-config --cflags --libs` -lz
3 Take one greek supported truetypefont (*.ttf) and copy it to the directory that the xine-fontconv is.
4 In the shell type:
./xine-fontconv font.ttf fontname iso-8859-1 iso-8859-2 iso-8859-15 iso-8859-7
*The above may generate some errors but it doesn't matter it will still work*
5 Become root and copy the resulted fonts (*.gz) in /usr/share/xine/libxine1/fonts/
6 Then run xine. Go to settings-setup-configuration experience level make yourself advanced, then go to subtitles, write your fonts name (eg freesans) and the encoding which is iso-8859-7
Thats it. :P

Now for mplayer i just copied one greek supported true type font in the .mplayer (hidden)directory. Then went to the preferences-subtitles & osd ,changed the encoding to iso-8859-7. Last went to font, browsed and chose the font that i copied and made the encoding UTF8.
Thats it.

I hope it helps.