Consegui reproduzir o problema que você está enfrentando. Eu fiz assim fazendo o seguinte:
$ gpg --no-default-keyring --keyring ./test-keyring --secret-keyring ./test-secring --trustdb-name ./test-trustdb --no-random-seed-file --gen-key
<specified parameters and let it do its thing>
gpg: key 58018BFE marked as ultimately trusted
public and secret key created and signed.
<snip>
$
Observe que o processo marcou a chave como "basicamente confiável".
Agora eu exporto as chaves:
$gpg --no-default-keyring --keyring ./test-keyring --secret-keyring ./test-secring --trustdb-name ./test-trustdb --no-random-seed-file --export-secret-keys -a >private.key
$gpg --no-default-keyring --keyring ./test-keyring --secret-keyring ./test-secring --trustdb-name ./test-trustdb --no-random-seed-file --export -a > public.key
Agora eu importo para um novo banco de dados gpg:
$gpg --no-default-keyring --keyring ./test2-keyring --secret-keyring ./test2-secring --trustdb-name ./test2-trustdb --no-random-seed-file --import public.key
$gpg --no-default-keyring --keyring ./test2-keyring --secret-keyring ./test2-secring --trustdb-name ./test2-trustdb --no-random-seed-file --import private.key
Agora, se eu tentar criptografar usando os novos chaveiros, obtenho:
$ gpg --no-default-keyring --keyring ./test2-keyring --secret-keyring ./test2-secring --trustdb-name ./test2-trustdb --no-random-seed-file -r Fake -e
gpg: AE3034E1: There is no assurance this key belongs to the named user
pub 1024R/AE3034E1 2013-06-13 Fake User <[email protected]>
Primary key fingerprint: AD4D BAFB 3960 6F9D 47C1 23BE B2E1 67A6 5801 8BFE
Subkey fingerprint: 58F2 3669 B8BD 1DFC 8B12 096F 5D19 AB91 AE30 34E1
It is NOT certain that the key belongs to the person named
in the user ID. If you *really* know what you are doing,
you may answer the next question with yes.
A razão para isso é o modelo "web of trust". Por padrão, para que uma chave pública seja confiável, ela requer um certificado de confiança "final" (normalmente onde você verificou pessoalmente as identidades das pessoas envolvidas) ou três certificados de confiança "marginais" (onde alguém que você conhece, quem conhece alguém que você conhece ... assinou o certificado).
Como o gpg é um aplicativo de segurança, ele avisa se você está tentando criptografar para uma chave que não está listada como confiável. A razão pela qual sua própria chave não é confiável nesse caso é simples. É porque você não exportou as relações de confiança da instância gpg anterior. Para fazer isso, use os comandos --export-ownertrust e --import-ownertrust.
Como sempre, consulte a página de manual .