I had similar issues with mplayer and xine (using smplayer and kaffeine, respectively). However, the problems just went away, and now both work. I still have problems with vlc, which is why I don't use it. However, if neither mplayer nor xine are working for you, perhaps you'll have better luck with
vlc.
Of course, as no2498 pointed out, sometimes a good frontend like smplayer can help with the backend (mplayer, in this case).
Otherwise, try "sudo dpkg-reconfigure mplayer" and see if that works (using the actual name of your mplayer package, of course).