yeah - mkv was always gonan be a stretch, but I can encode to quite litereally several HUNDRED difference combinations of avi / mpg / mpeg2 once you include all the different xvid and divx versions...
I'll start trying a few extra flavours, but though tI might get some advice here before I started coping every random file I could lay my hands on.
I'm assuming that it's not the resolution that's the the issue, just the codec... even my £200 nexus will play most resolution vids, even mkv's... it does struggle with 1080P Matroska's, but not much else.