Okay, I figured out the problem and have a fix. I don't believe this is a bug with dput-ng (so this issue can be closed), but instead it's a problem with the local user's trustdb. You'll have to fix your trustdb locally and then it should work. Here are a couple of links with some additional clues:
https://github.com/keybase/keybase-issues/issues/821 http://stuff-things.net/2015/04/22/gpg-public-key-of-ultimately-trusted-key-00000000-not-found/