Download the Essential Codecs package from the mplayers homepage http://www.mplayerhq.hu/design7/dload.html

Unzip and move to the directory: /usr/local/lib/codecs (create if it does not exist, need to use SUDO command)

Then run these two lines of code:
cd ~/.gnome2/totem-addons
for file in /usr/local/lib/codecs/* ; do ln -sf $file && chmod +r $file ; done