Daniel Patterson <dbp@dbpmail.net> writes:
>
> I click on it, and it requests _my_ public key from the key server, and
> of course nothing changes - because I already had the key.

So after you click, the key downloads, and the button does not change
colour?

> Any ideas? Is this because of some missing package or misconfigured
> setting? I'm using the latest released version of notmuch (0.15.2),
> emacs 24.2.1, and gpg 1.4.11.

Does using easypg from within emacs work for you? You can try with 
"M-x epa-list-keys"