Depending on kind of video file you are trying to play, you may need some GST plugins from the Universe or Multiverse repositories. You can enable them with:
sudo apt-add-repository universe
sudo apt-add-repository multiverse
sudo apt-get update
And then do the search again.