Is it me doing it wrong, or evolution never seems to work quite properly with seahorse? It never recognizes the signatures of people I trust. This is best conveyed through video screencasts, so you can take a look at the full-resolution version (ogg theora, 10 MiB): http://public.ecchi.ca/seahorse-evolution.ogg 

or, if your video card refuses to play the video because it's too big:
http://public.ecchi.ca/seahorse-evolution-small.ogg 

basically it shows some keys that I have marked as trusted (and even signed), but in evolution it complains that they cannot be authenticated; this is what evolution tells me: 
> gpg: armor header: Version: GnuPG v1.4.6 (GNU/Linux)
> gpg: Signature made Thu Jan 31 13:32:52 2008 EST using DSA key ID 08BA5E1B
> gpg: using PGP trust model
> gpg: Good signature from "David Haguenauer <david@kurokatta.org>"
> gpg: Preferred keyserver: http://www.kurokatta.org/doc/david.asc
> gpg: WARNING: This key is not certified with a trusted signature!
> gpg:          There is no indication that the signature belongs to the owner.
> Primary key fingerprint: B0A9 87A9 4A90 3C9F 2CE0  1671 817E 4D45 08BA 5E1B
> gpg: textmode signature, digest algorithm SHA1

As Adam suggested, here is the output of gpg --edit-key 08BA5E1B: 
> pub  1024D/08BA5E1B  created: 2004-08-25  expires: 2016-01-20  usage: SC  
>                      trust: full          validity: unknown
> sub  1536g/5455FA00  created: 2004-08-25  expires: 2012-08-23  usage: E   
> [ unknown] (1). David Haguenauer <david@kurokatta.org>

More troubleshooting:
> sadam: there's the problem, trust is full, but the validity's not set
> you're supposed to do that when you sign the key
> nekohayo: uh... but I did sign the key.
> sadam: you have both boxes checked on the trust tab of David's key's properties?
> nekohayo: yes
> sadam: in the sign key dialog, you have to set how carefully you checked the key
> nekohayo: yeah, I checked it "very seriously" :)


Please save my poor soul, I've been trying to understand this mess for months :)