Thanks for the replies.

I've used Avidemux to reencode from mkv(AVC1) to avi (Xvid) and it plays nicely on N900.

But one problem remains, the mkv files contained optional subtitles that didn't transfer. What would be easiest way (on Linux) to reencode them also? (hard code them directly on the video would be Ok)