evolution does not seem to trust keys that are signed in seahorse

[Jeff <web kiddo free fr>]

I chatted a bit with Adam S. on IRC and could not find out what's wrong exactly, so I'll be pasting bits of conversation here.
Basically: is it me or seahorse never seems to work quite properly with evolution? 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 http://public.ecchi.ca/seahorse-evolution-small.ogg if your video card refuses to play this; usually certain intel GPUs with Totem).

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> sadam: uh... but I did sign the key. a bug in seahorse? or something I forgot to do besides signing?
>     <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 :) you can c.c. me at nekohayo at gmail as I may reply a lot slower on this account.