I have recently posted about Seveas’ Repository, which includes a comprehensive package for multimedia within gnome or kde. I also wanted to outline how you can manually install most of the main multimedia codecs for your ubuntu machine. (I personally still prefer the manual method as there are a few aspects of Seveas’ multimedia package that I don’t like.)
Install Multimedia Codecs for Ubuntu
sudo aptitude install gstreamer0.10-pitfdll gstreamer0.10-ffmpeg gstreamer0.10-gl gstreamer0.10-plugins-base gstreamer0.10-plugins-good gstreamer0.10-plugins-bad gstreamer0.10-plugins-bad-multiverse gstreamer0.10-plugins-ugly gstreamer0.10-plugins-ugly-multiverse libxine-extracodecs w32codecs
Everything included in these multimedia codec packages should give you complete playback ability for most known codecs.
Note: the above command should be inputted on one line. Also, a few of these codecs are not yet supported for amd64 users.