For version older than 4.4.9:
These files ("gallery-template.php" and "gallery-single-template.php") should be located in your theme folder in order to make it work with your theme. Theme folder is totally replaced with a new folder/files after updates. That is why you get this error after updating your theme.
When updating your theme, copy these template files from Gallery plugin folder
to your theme folder
If you are updating the active theme, you can deactivate and activate Gallery plugin in order to copy these files automatically.