У меня тоже самое было. Я весь избился, и ставил и удалял и плееры и кодеки. Скорее всего mplayer окривел в репах.
Перезапустился в ранее установленную Kubuntu, там работает.
Начал выяснять в чем дело, оказалось что mplayer и smplayer установлены svn, а в новой кубунте не из svn реп.
Svn репы гуглением не нашел, поэтому взял реп из старой Kubuntu и вставил в новую, и все заработало.
Вообще то я весь source list из старой Kubuntu в новую запихал.