Ubuntu Server apt update Error after 14.04 to 16.04 Upgrade

I finally updated my Ubuntu 14.04 LTS server to 16.04.1 LTS. It took a while and after fixing some website issues things were looking good.

apt update Error

However, an error occurred when performing an sudo apt update. Both apt and apt-get gave the following.

Hit:2 http://archive.ubuntu.com/ubuntu xenial InRelease
Get:1 http://security.ubuntu.com/ubuntu xenial-security InRelease [102 kB]
Get:3 http://archive.ubuntu.com/ubuntu xenial-updates InRelease [102 kB]           
Err:2 http://archive.ubuntu.com/ubuntu xenial InRelease      
Could not execute 'apt-key' to verify signature (is gnupg installed?)
Err:1 http://security.ubuntu.com/ubuntu xenial-security InRelease
Could not execute 'apt-key' to verify signature (is gnupg installed?)
Err:3 http://archive.ubuntu.com/ubuntu xenial-updates InRelease
Could not execute 'apt-key' to verify signature (is gnupg installed?)
Fetched 204 kB in 0s (3,299 kB/s)
Reading package lists... Done
Building dependency tree       
Reading state information... Done
All packages are up to date.
W: An error occurred during the signature verification. The repository is not updated and the previous index files will be used. GPG error: http://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://security.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://archive.ubuntu.com/ubuntu xenial-updates InRelease: Could not execute 'apt-key' to verify signature (is gnupg installed?)
W: Failed to fetch http://archive.ubuntu.com/ubuntu/dists/xenial/InRelease  Could not execute 'apt-key' to verify signature (is gnupg installed?)
W: Failed to fetch http://archive.ubuntu.com/ubuntu/dists/xenial-updates/InRelease  Could not execute 'apt-key' to verify signature (is gnupg installed?)
W: Failed to fetch http://security.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.

Solution

There was not much online help regarding this error, some mention problems with permission on /tmp.

Update Kernel with Digital Ocean

I fixed this issue by going to the Digital Ocean kernel page for my droplet and, after much trial and error, I found that the
DigitalOcean GrubLoader v0.2 (20160714) Ubuntu kernel worked after rebooting.

Now sudo apt update works!