Recently I've moved to a new laptop, and for the longest time I haven't been able to figure out why I couldn't sign my messages with gpg any more (I'm on keybase as sbrl). Turns out the problem was that gpg didn't 'trust' my private key. This post documents how I fixed it:

# First, import your private key into gpg (you've probably done this already)
gpg --import <secret_key.priv
# Then, get gpg to edit your private key, and ask it to trust your private key
gpg --edit-key toaster5@waffletoast.net
> trust
> 5
> y

Once done, you can then select your private key in evolution in the preferences (SHIFT + CTRL + S).

Did this help you out? Still having issues? Let me know in the comments below!