I recently ran into “The template you have chosen is invalid or cannot be found” while creating a site from a template moved from another SharePoint server. The most likely cause is a missing feature on the destination server.
A recent source of this problem has been two recent updates, "Infrastructure Updates to MOSS 2007" and MOSS Service Pack 2 and a feature named S2SiteAdmin.
To find the missing feature use this great tool from CodePlex.com: “STP Inspector” http://stpinspector.codeplex.com/
This tool will list all of the features needed by the STP file and flag those missing on the SharePoint server.
Note: this tool must be run on the server where you want to use the site template (STP) file.