Instalas Feisty, y tienes que instalar el soporte para la reproducción de archivos de vídeo y música, no cuentas con Automatix, pues este comando te instala entre Basico y completo soporte para la reproducción de audio y vídeo en varios formatos, como en la mayoría de los casos, debemos tener habilitada toda la lista de recursos del archivo sources.list, abrimos consola y ejecutamos:

:~$ sudo apt-get install gstreamer0.10-plugins-base gstreamer0.10-plugins-good alsa-oss faac faad ffmpeg gstreamer0.10-ffmpeg gstreamer0.10-fluendo-mp3 gstreamer0.10-fluendo-mpegdemux gstreamer0.10-gl gstreamer0.10-gnonlin gstreamer0.10-plugins-bad gstreamer0.10-plugins-bad-multiverse gstreamer0.10-plugins-ugly gstreamer0.10-plugins-ugly-multiverse gstreamer0.10-sdl lame liba52-0.7.4 libartsc0 libavcodec0d libavformat0d libcurl3-gnutls libdc1394-13 libdvdread3 libfaac0 libfaad2-0 libgsm1 libid3tag0 liblame0 libmad0 libmjpegtools0c2a libmms0 libmodplug0c2 libmp4v2-0 libmpcdec3 libmpeg2-4 liboggflac3 libquicktime0 libsidplay1 libswfdec0.3 libvorbisfile3 libxine-extracodecs libxine-main1 libxine1 libxvidcore4 libxvmc1 mjpegtools mpg321 sox totem-xine vorbis-tools

tratare de editar esta entrada con el fin de completar el soporte de distintos formatos.

si acabas de actualizar a Feisty desde Edgy (7 Abril) sale un error, estoy viendo la manera de instalar los paquetes.

ya esta!! no hay truco, solo intentas reproducir el archivo multimedia y automáticamente te ofrece instalar los codecs para el perfecto funcionamiento, te dejo dos pantallazos para que te des una idea, suerte.

Actualizado, !! para los que instalaron apenas apartir del 18 de Abril :

/multimedia-en-ubuntu-feisty-fawn-facil-linux/