#urpmi faac faad2 gstreamer0.10-faac gstreamer0.10-faad
но перед этим подключите
в дистрибутивах по 2010.2 репозитории PLF
в 2011 restricted на http://urpmi.mandriva.ru
посмотрите так же установлены ли ffmpeg, mplayer, mencoder

Под KDE есть Dragon Player - берёт всё кроме внешних субтитров (встроенные в mkv - нормально, на себе проверено). Есть соответствующая надстройка к Mplayer - KMplayer. Эта связка берёт вообще всё кроме linked-mkv (встречается в раздачах сериалов, в частности аниме). Кстати, а проблема именно в mkv-контейнере или в кодеке h.264, который там часто встречается? Если в контейнере, попробуйте поставить пакет mkvtoolnix - это набор инструментов для создания mkv, он должен потянуть по зависимостям все нужные библиотеки, если они там отдельно собраны (в KUbuntu всё было собрано вместе, как в Mandriva не знаю). Посмотрите, подключен ли "несвободный" раздел репозитория - без него поддержки h.264 точно не будет. Наконец попробуйте Mplayer2 - это форк классического Mplayer. Выпускается в исходниках и в виде статической бинарной сборки (всё в одном файле, включая все кодеки и контейнеры). Кстати, только он поддерживает linked-mkv - на это сам уже нарвался. То есть просто положить этот бинарник в удобное место и перенастроить на него надстройку KMplayer для удобного запуска из-под KDE. По поводу VLC - должен он быть, если не видно, скорее всего таки не все разделы репозитория подключены.

Спасибо всем, кто ответил мне, особенная благодарность Дмитрию...проблему устранил доустановкой репозитория