Try adding the following line to your /etc/apt/sources.list file and replace "testing" with your favorite choice of stable, testing, or unstable. It's unofficial .debs of mplayer, lame and other such goodies from Christian Marillat. You can also get xine from there, which is similar to mplayer.

deb     http://www.debian-multimedia.org sid main

or

deb     http://www.debian-multimedia.org testing main