Disclaimer: before following these instructions, check your local laws to see if it is legal to install giflib, which contains LZW compression, in your local jurisdiction.
In short, giflib is essentially uninstallable in ubuntu because it is marked as conflicting with libungif, which mplayer, mencoder, ffmpeg, and other programs depend on explicitly. Until those depends are changed to libungif4g | libgif4, here's how you can fool dpkg into thinking you have libungif4g but still have giflib (and it's LZW compression) installed.
Since the two are binary compatible, just mark libungif as held, remove its contents, install libgif, and symlink libungif* to libgif* :
echo "libungif4g hold" | sudo dpkg --set-selections #you'll get some errors rm'ing directories in the next step, that's ok dpkg -L libungif4g | while read X ; do sudo rm -f "$X" ; done cd ~/src || cd /tmp wget http://skibrianski.googlepages.com/giflib-4.1.4-2-sid-patched.tgz tar xfz giflib-4.1.4-2-sid-patched.tgz cd giflib-4.1.4 sh configure && make && sudo make install cd /usr/lib for i in /usr/local/lib/libgif.so* ; do sudo ln -s $i ; base=`echo $i | sed 's/^.*\///'`; sudo ln -s $base `echo $base | sed 's/libgif/libungif/'` ; done
If mplayer with no arguments doesn't immediately bomb out on you, you're done.