GnuPG warning for a signed key with trust level 4

The message says GnuPG could not validate the key issuing a correct signature. With other words, you know that the signature was indeed issued by a given private key, but are not sure who actually issued this key.

Trust in GnuPG is only relevant when validating keys based on certifications in the OpenPGP web of trust, also read up on "What is the exact meaning of this gpg output regarding trust?". The trust level defines how much you put trust in the key owner's certifications on other keys, but requires already validated keys. For example if issued on an already-validated key, trust level four ("full trust"), by default defines all keys certified by the valid and fully trusted key to be also valid.

"Ultimate trust" (level five) is special: it is used as introducer when validating keys, thus makes the key validated and always considers other keys certified by this key as validated. This should never be used on keys not issued by yourself, gpg --edit-key and sign other's keys instead of issuing trust (after verifying the key in fact belongs to that party). If you do not want to issue a public certification, there's also lsign for issuing local signatures that GnuPG does not export when sharing a public key.

The warning is shown always excepting for your own keys (level 5), accepted by 'per se'.

The gpg trust levels are explained here: https://gpgtools.tenderapp.com/kb/faq/what-is-ownertrust-trust-levels-explained

You have assigned a trust level to a key that has not been verified yet. Verification works by finding a path of trustworthy keys from a key with ultimate trust (which should be your own key) through signatures made by trusted keys to the key being verified.

In your case, the trust path is rather short, since you have signed the key. Since it's not showing as verified, this means that your own key is not marked as trusted.

By marking the other person's key as trusted, all keys they sign are now also marked as verified.