Para saber mais sobre o problema, não confie na mensagem de erro do Kleopatra .
Executando o gpg2.exe na linha de comando, recebi o seguinte:
gpg: key C0D3AFD2 was created 1810 seconds in the future (time warp or clock problem)
[...]
gpg: key C0D3AFD2: no valid user IDs
gpg: this may be caused by a missing self-signature
[...]
gpg: Total number processed: 2
gpg: w/o user IDs: 2
Portanto, as assinaturas estão sendo recusadas porque a hora / data está errada!
Com certeza, o relógio da máquina Linux que criou as chaves foi definido para duas horas no futuro ...