Problem with keys imported via DNS CERT

[Robert J. Hansen]

Alex wrote:
> No, I am starting out with a clean ~/.gnupg folder.

There's your problem.  Set the key to implicit trust and see if the 
problem goes away.