É um bug conhecido discutido aqui .
Arquivos avi colocados na pasta Vídeo aparecem quase que imediatamente, mas por algum motivo, os mp4 não.
O Movie Player reproduzirá o mp4, então não acho que seja uma situação instável.
Aqui está o que sempre faço para o melhor suporte ao codec:
sudo wget http://www.medibuntu.org/sources.list.d/'lsb_release -cs'.list --output-document=/etc/apt/sources.list.d/medibuntu.list; sudo apt-get -q update; sudo apt-get --yes -q --allow-unauthenticated install medibuntu-keyring; sudo apt-get -q update
sudo apt-get install non-free-codecs