The template you have selected is invalid or cannot be found

We were trying to create a site collection using a template uploaded in to Global template gallery using the stsadm command. But while creating the site collection we were getting the following error.

"The template you have selected is invalid or cannot be found"

After some investigation, again this is due to the Publishing feature. We deactivated the "Publishing feature" in the source site. Recreated the template. Uploaded it again using the Stsadm command. Now the site collection got created successfully.