The template you have chosen is invalid or cannot be found

I received the error “The template you have chosen is invalid or cannot be found” when trying to create a new site from a custom site template.

Normally when this error occurs it is due to a dependent feature that has not been installed.
I came across this nifty tool, STP Inspector, that shows dependencies for a STP file on the site features and site collection features.

Run the tool, identify the missing features and install them.
Problem sorted.