Você só precisa instalar os plugins gstreamer que incluem os codecs h264:
➜ ~ apt-cache show gstreamer1.0-plugins-ugly | grep Gstreamer-Encoders
Gstreamer-Encoders: audio/AMR; audio/mpeg, mpegversion=(int)1, layer=(int){ 3, 2 };
video/x-h264, stream-format=(string){ avc, byte-stream },
alignment=(string)au, profile=(string){ high-4:4:4, high-4:2:2, high-10,
high, main, baseline, constrained-baseline, high-4:4:4-intra, high-4:2:2-intra, high-10-intra }
Então, basta executar:
sudo apt-get install gstreamer1.0-plugins-ugly
ou
sudo apt-get install gstreamer0.10-plugins-ugly
e pronto. Você não precisa instalar mais nada, nem usar o pacote ubuntu-restricted-extras.