gpg: WARNING: message was not integrity protected
Solution 1:
There are two different warnings here, and I think the other responders are assuming the one is caused by the other.
I assume the "message was not integrity protected" warning is your main concern, since that's the title of this question. There seem to be several things that can cause that, but the one I just encountered is when GPG's "MDC protection" feature isn't enabled. I don't know what it stands for, but apparently it's a message integrity check that proves the message hasn't been tampered with.
Apparently this feature is on by default, but gets disabled if any of the recipient keys don't specify they support it. So I just got the warning for the first time when adding a new recipient to a file I'd previously been encrypting only to myself, presumably because the new recipient didn't say they supported MDC.
I got the warning to go away by adding --force-mdc
to my GPG command. I haven't yet discovered whether this prevents the new recipient from decrypting the message...
I'm pretty sure the other warning, about the key not being trusted, is unrelated to the "not integrity protected" warning.
Solution 2:
In gpg, you don't yet 'trust' the sender. So even though it's from yourmate@whatever, you haven't set their trust level in gpg to whatever it needs to be to not get that message :)
At least that's what I think; could be wrong. GPG docs should help though.