Hola, lo primero que tienes que hacer es descargarte Ubuntu Tweak, que es un programa que te ayuda a tener estupendamente configurado Ubuntu. Vas a su pagina oficial (
http://ubuntu-tweak.com/), te lo descargas(es un .deb), le haces doble clic y ya lo tendrás instalado.
Cuando lo hayas instalado, lo tendrás en Aplicaciones--->Herramientas del Sistema--->Ubuntu Tweak
Entras dentro del programa, y después de echarle un vistazo general, te metes en el Centro de Aplicaciones, y buscas una que pone "Extras restringidos de Ubuntu", la marcas y lo instalas. Este paquete contiene los codecs necesarios para ver toda clase de videos.
Además, te aconsejo que mires si tienes instalada la última versión de VLC, que es la 1.1.4, ya que en Herramientas--->Preferencias---->Entrada y Codecs, tienes una casilla que pone "Usar aceleración GPU(Experimental)", por si la quieres marcar. Quizá ayude en algo.
También puedes pasar de Ubuntu Tweak(no te lo recomiendo), y poner en la consola : sudo aptitude install ubuntu-restricted-extras de este modo te instalará el paquete de codecs en cuestión.
Saludos.