One answer is you could sign the key.

gpg --edit-key YOUR_RECIPIENT

sign

yes

save

The other is you could tell gpg to go ahead and trust.

gpg --encrypt --recipient YOUR_RECIPIENT --trust-model always YOUR_FILE