why is apt-get update saying can't execute apt-key?

Since upgrading to Ubuntu 16.04.01, every time I try apt-get update, I see:

W: GPG error: http://security.ubuntu.com/ubuntu xenial-security InRelease: Could not execute ‘apt-key’ to verify signature (is gnupg installed?)

With chattr +a /tmp and apt-get -o “Debug::Acquire::gpgv=true” update, I tried rerunning apt-key by hand with the same arguments, and it runs fine.

I created a new droplet with 14.04 and upgraded it to 16.04 and it works fine.