А что написано в спецификациях на телефон - какие форматы видеофайлов он должен проигрывать? Сильно сомневаюсь, что там присутствует mkv.
посмотреть, какое видео проигрывается без проблем и перекодировать нужные ролики согласно типу этого видео. Вообще, обычно у каждого производителя есть некое промежуточное приложение (например, у Нокии - Nokia PC Suite), которое автоматически преобразует видео в нужный формат во время копирования на телефон.
