if I may speak about my opinion: Forget mplayer and use xine ;-)
I didn't try it in ubuntu, but I found xine much better and more uncomplicated than mplayer.
Personal opinion, too, surely
With KDE: sudo adept, search for xine-ui in the filter field
With Gnome: sudo synaptic, again: search for xine-ui
Maybe, you have to enable the universe tree into your /etc/apt/sources.list.
And don't forget the codecs, Agrouf mentioned.
Hope this one helps,