As David intimated, the problem here is that gpg doesn’t trust the public key you’re using to encrypt. You could sign the key as he explained.
An alternative–especially if the key might be changing occasionally–would be to tack on --trust-model always to your gpg command.
Here’s the relevant bit from the man page:
--trust-model pgp|classic|direct|always|auto Set what trust model GnuPG should follow. The models are: pgp This is the Web of Trust combined with trust signatures as used in PGP 5.x and later. This is the default trust model when creating a new trust database. classic This is the standard Web of Trust as used in PGP 2.x and earlier. direct Key validity is set directly by the user and not calculated via the Web of Trust. always Skip key validation and assume that used keys are always fully trusted. You generally won't use this unless you are using some external validation scheme. This option also suppresses the "[uncertain]" tag printed with signature checks when there is no evidence that the user ID is bound to the key. auto Select the trust model depending on whatever the internal trust database says. This is the default model if such a database already exists.