Harry Pfleger had this problem with the first v3 Application Template to be issued (GroupBoard) but it will apply to all v3 application templates.
He solved it with
stsadm -o deploysolution -name gbw.wsp -url http://myurl
-immediate -allowgacdeployment -force
Note: This will clear that and the template will now be listed but there may "access denied" when trying to create the template.
This seems to be related to the account used for the site collection administrator - try using a domain account.
Anyone with a definitive answer, please send me mail or a comment to this item at the collutions WSS FAQ site.