"Key invalid" means that you haven't signed the key, and therefore confirmed that the key actually belongs to that user. This is a warning and can be ignored if you so wish (the encryption will succeed).
See the section on "Invalid Keys" in Appendix C ("Frequently Asked Questions") of the PGP Command Line User's Guide.
This should only apply to public keys. Once you set implict trust on a keypair, it should no longer be considered invalid. Do you have a key pair that has implicit trust but is sitll considered invalid? What is the output of running "pgp --list-keys [userid of invalid keypair]"?
Thanks,