Para poder reproduzir a maioria dos formatos de áudio e vídeo, instale o Ubuntu Restricted Extras:
sudo apt-get install ubuntu-restricted-extras
Editar
Para descobrir qual codec você precisa:
sudo apt-get install libav-tools
ffprobe -show_streams "file.mp4"
Provavelmente será AAC para audo e H.264 para vídeo.
O suporte para decodificar MPEG-4 AAC
é fornecido por gstreamer1.0-libav e para decodificar H.264
existe gstreamr0.10-ffmpeg :
sudo apt-get install gstreamer1.0-libav gstreamer0.10-ffmpeg