Removing the _apt user as a suggested work-around does not work for me on Ubuntu Server upgraded fro 14.04 to 16.04.
This is what I see: root@XXX:~# apt-get update Hit:1 http://us.archive.ubuntu.com/ubuntu xenial InRelease Err:1 http://us.archive.ubuntu.com/ubuntu xenial InRelease Could not execute 'apt-key' to verify signature (is gnupg installed?) Hit:3 http://us.archive.ubuntu.com/ubuntu xenial-security InRelease Err:3 http://us.archive.ubuntu.com/ubuntu xenial-security InRelease Could not execute 'apt-key' to verify signature (is gnupg installed?) Get:2 http://us.archive.ubuntu.com/ubuntu xenial-updates InRelease [95.7 kB] Err:2 http://us.archive.ubuntu.com/ubuntu xenial-updates InRelease Could not execute 'apt-key' to verify signature (is gnupg installed?) Fetched 95.7 kB in 0s (147 kB/s) Reading package lists... Done W: No sandbox user '_apt' on the system, can not drop privileges W: An error occurred during the signature verification. The repository is not updated and the previous index files will be used. GPG error: http://us.archive.ubuntu.com/ubuntu xenial InRelease: Could not execute 'apt-key' to verify signature (is gnupg installed?) W: An error occurred during the signature verification. The repository is not updated and the previous index files will be used. GPG error: http://us.archive.ubuntu.com/ubuntu xenial-security InRelease: Could not execute 'apt-key' to verify signature (is gnupg installed?) W: An error occurred during the signature verification. The repository is not updated and the previous index files will be used. GPG error: http://us.archive.ubuntu.com/ubuntu xenial-updates InRelease: Could not execute 'apt-key' to verify signature (is gnupg installed?) W: Failed to fetch http://us.archive.ubuntu.com/ubuntu/dists/xenial/InRelease Could not execute 'apt-key' to verify signature (is gnupg installed?) W: Failed to fetch http://us.archive.ubuntu.com/ubuntu/dists/xenial-updates/InRelease Could not execute 'apt-key' to verify signature (is gnupg installed?) W: Failed to fetch http://us.archive.ubuntu.com/ubuntu/dists/xenial-security/InRelease Could not execute 'apt-key' to verify signature (is gnupg installed?) W: Some index files failed to download. They have been ignored, or old ones used instead. -- You received this bug notification because you are a member of Ubuntu Bugs, which is subscribed to Ubuntu. https://bugs.launchpad.net/bugs/1577926 Title: apt-key works fine, yet apt fails with "Could not execute 'apt-key'" To manage notifications about this bug go to: https://bugs.launchpad.net/ubuntu/+source/apt/+bug/1577926/+subscriptions -- ubuntu-bugs mailing list ubuntu-bugs@lists.ubuntu.com https://lists.ubuntu.com/mailman/listinfo/ubuntu-bugs