Mate-1.0.8-3 - это единственный плейер, который споткнулся на mp4. Проверил ещё из репы Xine и Ghine - нормально. На еже у меня давно стоит SnowDog - ОК. И который выложил вчера - в порядке, иначе бы не заморачивался.
VLC использует свои собственные кодеки, а что тянет Ffmpeg, так только пару-другую библиотек. Могу точнее. Проверял на ходовых у меня форматах: avi, mp4, flv, mts (есть и другие, надо найти). Общие библиотеки, нужные для всех - libavcodec и libavutil. Для flv понадобилась libavformat. Всё.