I also can't seem to enable visual effects etc, so I'm thinking maybe it might have something to do with video drivers rather than a codec problem? In the hardware drivers application (in system --> administration) it says there are no proprietary drivers in use.
That's normal if you don't have hardware that requires proprietary drivers.
Ubuntu has a convenient package that installs most the non-free programs people commonly want, including many codecs.
sudo apt-get install ubuntu-restricted-extras
What you need depends on the video player you use. The default, Totem, as well as Banshee and a couple of others use gstreamer. These should be installed with the above.
Kaffeine, I believe Dragon, and some others use xine. I believe this should get you what you need there
sudo apt-get install libxine1-all-plugins
Mplayer is its own thing. Enable the medibuntu repository
to get extra mplayer codecs and libdvdcss, necessary for any app to play commercial DVDs, plus an unstripped version of libavcodec, the library for ffmpeg.
sudo apt-get install libdvdcss2 non-free-codecs libavcodec-unstripped-52