Avi e MP4 são formatos proprietários, então você precisa instalar o Ubuntu Restricted Extras. A partir da descrição do pacote: "[Instalações] Aplicativos comumente usados com direitos autorais restritos (mp3, avi, mpeg, TrueType, Java, Flash, Codecs)"
Abra o Ubuntu Software Center e pesquise "Extras Restritos do Ubuntu"