Well, if you can get vlc player running on YD then .mkv files should play fine.
http://www.videolan.org/vlc/
I have played mkv in the PS3 just using xmb. Obviously I had to do a conversion of the video files, but to get mkv to play you do not have to re-encode the whole video. so the actual conversion is less than 10 mins. Then just copied onto a USB stick, plays back flawlessly. Obviously not everyone is happy to re-encode their files if they have lots, but it is very quick using pspvideo9.
As far as I know you cannot run 720p mkv files in Linux yet without excessive jerking.
rp2000
Thanks rp2000, do subtitles work though? thats the most important thing for me...
No they don't (I assume you mean seperate subtitle files that you would load using VLC or Media Player Classic etc).
rp2000