Do you still remember PGP 2? When you added a key or changed trust parameters, it would automatically detect that some keys got certified, and would ask you whether you considered these keys’ holders trustworthy. GnuPG is lacking this feature: You’ll have to use the key editing menu in order to adjust trust levels of any keys for which you consider this appropriate. Of course, this is cumbersome – in particular when you add keys to your key ring routinely, and keeping track of trust levels is not an option.
This script may help you to assign trust levels: It will look for keys on your keyring which carry well-certified user IDs, but haven’t had any owner trust level assigned to them. It will then run gpg –edit over all these keys and allow you to nicely adjust trust levels.