You don't mention your hardware, but vlc's default video output setting works for me on Intel graphics and, possibly, on ATI/AMD cards with the open source xorg driver. It doesn't work at all on ATI/AMD with the propietary driver. In that case, pick the opengl setting which is hardware accelerated with this driver, not X11, which is slow. Normally, and AFAIK, the default picks xvideo, which is accelerated on Intel and others. I have no idea regarding Nvidia hardware, so someone else would have to chip in...