Notei algo estranho aqui comigo, agora há pouco...
Três dias atrás, eu instalei o Ubuntu 12.04 no notebook de um conhecido, deixando o Unity como modo gráfico padrão. Instalei ubuntu-restricted-extras, o VLC, o GNOME-MPlayer e uma série de codecs específicos do Totem, necessários para ele reproduzir vídeos nos mais diversos formatos (que no meu caso seria os pacotes de nome começando com 'gstreamer0.10-plugins').
Nessa segunda-feira, dia 7, foi que notei esse problema que você está tendo agora, que é dos vídeos em MP4 não tendo miniaturas geradas nem sendo possível reproduzí-los no Totem. Não dei muita trela pra isso, pois pra esses casos em particular posso usar os outros reprodutores de vídeo.
No entanto, hoje dia 10, decidi fazer um rápido teste na minha máquina do trabalho usando uns vídeos MP4 de umas videoaulas que fiz para ensino à distância. Instalei nesse pc os mesmos programas e pacotes que instalei no notebook na segunda-feira, logo imaginei que ao abrir os vídeos, o problema das miniaturas também fosse acontecer aqui. Mas não foi o caso: os vídeos tanto foram reproduzidos normalmente, como tiveram suas miniaturas geradas sem mais problemas.
Não sei ao certo o porquê dos vídeos MP4 terem sido reproduzidos / tido miniaturas geradas, mas tenho três hipóteses:
1. O problema talvez aconteça apenas em arquitetura 64-bits e não em 32-bits (improvável);
2. O problema não acontece com qualquer vídeo em MP4, apenas em alguns casos. Isso depende muito dos codecs de áudio e vídeo utilizados, ou da forma como foram encodados;
3. No decorrer dessa semana, praticamente todo dia tem saído atualizações do Ubuntu 12.04 Precise pra baixar. Talvez nas últimas 48 horas, as atualizações mais recentes lançadas tenham resolvido esse problema, e como instalei atualizações tanto ontem como hoje, imagino isso ser a causa dos vídeos terem reproduzidos normalmente.
Assim sendo, tente instalar as atualizações mais recentes do Ubuntu e reinicie seu computador. Talvez resolva essa questão.