Open up GMPlayer (or another MPlayer GUI) right-click on it, go to Preferences, click on the Font tab and from the Encoding list chose Slavic/Central European Languages (ISO-8859-2) for Romanian subtitles. Use Modern Greek (ISO-8859-7) for Greek subtitles. Be sure to also pick a font that contains the specific diacritic character sets (Verdana and Arial can be found in the msttfcorefonts package in most Linux distributions and proved to be almost perfect for this task). Even better, be sure you installed the mplayer-fonts package and leave the font field empty for the application to chose it’s own system font.
If you don’t use a GUI for MPlayer and prefer the CLI way, you can set the encoding with the -subcp attribute.