I don't know if this will fix it in Ubuntu, but what I do in Debian Etch is I download the "essentials" codec pack from mplayer's web page. You uncompress the folder, and then copy the contents to /usr/lib/win32/ using the following commands:
sudo mkdir /usr/lib/win32/
sudo cp * /usr/lib/win32/
This will create the directory /usr/lib/win32/ if it doesn't exist (if it does, then the mkdir command will fail but that's okay). Then it will copy the files over, giving them the proper root:root ownership and also making the file permissions the default 644.
After these codecs are copied over, pretty much any video will play in Kaffeine.