I must still be missing something but now I got a little farther into looking up the certificates. It seems to be as though evolution is supposed to load built-in certs from NSS from the nssckbi.so file; which comes from /usr/lib/<triplet>/nss. Unfortunately, evolution uses nss's libdir directly to look for nssckbi, so it probably just looks for it in one directory too low (missing "/nss"). Seems like this is probably something that changed in NSS itself, but I'll first verify this with a test patch in evo.
I did get that dialog too.
I must still be missing something but now I got a little farther into looking up the certificates. It seems to be as though evolution is supposed to load built-in certs from NSS from the nssckbi.so file; which comes from /usr/lib/ <triplet> /nss. Unfortunately, evolution uses nss's libdir directly to look for nssckbi, so it probably just looks for it in one directory too low (missing "/nss"). Seems like this is probably something that changed in NSS itself, but I'll first verify this with a test patch in evo.