Basicamente, tudo o que é necessário está aqui:
arj faac faad ffmpeg ffmpeg2theora flac flashplugin-installer gstreamer0.10-ffmpeg gstreamer0.10-plugins-bad gstreamer0.10-plugins-ugly icedax id3v2 lame lha libdvdcss2 libflac++6 libjpeg-progs libmpeg3-1 mencoder mjpegtools mp3gain mpeg2dec mpeg3-utils mpegdemux mpg123 mpg321 p7zip p7zip-full p7zip-rar regionset sox ubuntu-restricted-extras unace-nonfree unrar rar uudeview vorbis-tools x264
O non-free-codecs é o mesmo caso do w64codecs, recentemente deixou de existir.
Obs.: uma boa opção para ter um pacote completo de softwares e codecs multimedia é instalar o ubuntustudio-desktop. Ele vai instalar o ambiente xfce também, mas não é obrigatório a usar. O Ubuntu Studio é um sabor do Ubuntu voltado para trabalhos artísticos em geral, seja edição de áudio/vídeo, edição de imagens e etc... é o que eu uso, por exemplo.