Oh hey, I did it. Found out what's happening: Xine uses its own fonts. Totem uses the system's FreeType fonts.
To tell Xine to use a FreeType font for subtitles, find and set these like so in xine.conf:
subtitles.separate.font_freetype:/usr/share/fonts/truetype/freefont/FreeSansBold.ttf
subtitles.separate.font_use_freetype:1
subtitles.separate.src_encoding:iso-8859-7
Reference:
http://www.xine-project.org/faq#supportedfontsYou don't even need language-support-el.