If you have already followed and and a video still cannot be played, open a terminal window and enter the command totem --help-gst. This will show a list of available options you can use to get debug output. Often the problem is in an underlying plugin, for example in GStreamer and not in Videos itself.