Two things to check:
1. Rights. The person creating the custom template-based document
library must be in one of the four built-in Site Groups in the top-level
site. I know it sounds weird but there are ACLs that will prevent the
display of custom templates even if the user is an Administrator on the
site where the creation will take place. Unless they are at least a
Reader on the top-level site they won't see the template.
2. Site Definition. The custom template will only be visible on sites
that are based upon the same site definition as the site where the
template was generated. So, for instance, you can't use meeting
workspace templates in a team site or any portal area.