On Ubuntu 16.04 64-bit, I found that I needed to install a few extra libraries to get the Video library to work, including an older version of libgstreamer.

sudo apt-get install libgstreamer0.10-dev libgstreamer-plugins-base0.10-dev gstreamer0.10-plugins-good

After that, everything worked great 😀.