En gsmspain han hablado esta mañana de un reproductor de vídeo que está en el Market llamado MoboPlayer.
No lo he probado aún, pero lo cito porque por lo que se vé un su Web y en su propia página del Market parece un gran reproductor de videos, que puede con casi todos los formatos existentes y tiene una buenísima interfaz.
Espero que mi comentario te sea de utilidad.
Saludos.