Relevant: During install I already clicked the box to allow restricted content. Recently I also installed ubuntu-restricted extras. These videos used to work on previous install with no problem. Formats are mp4, webm, and avi.
The error is "Totem could not startup. Some necessary plug-ins are missing. Make sure that the program is correctly installed".
sudo apt-get install --reinstall totem
to reinstall Totem and see if that solves it.