I rebuilt my /etc/apt/sources.list
with help from https://askubuntu.com/questions/124017/how-do-i-restore-the-default-repositories. My sources.list had some of my custom ones and the Linode mirrors. I just replaced my sources.list with the output from https://repogen.simplylinux.ch. I ran the upgrade again and it succeeded.
Example from my sources.list that failed
## Major bug fix updates produced after the final release of the
## distribution. deb http://mirrors.linode.com/ubuntu/ xenial-updates main restricted
# deb-src http://mirrors.linode.com/ubuntu/ xenial-updates main restricted
## N.B. software from this repository is ENTIRELY UNSUPPORTED by the Ubuntu
## team. Also, please note that software in universe WILL NOT receive any
## review or updates from the Ubuntu security team. deb
http://mirrors.linode.com/ubuntu/ xenial universe
# deb-src http://mirrors.linode.com/ubuntu/ xenial universe deb
http://mirrors.linode.com/ubuntu/ xenial-updates universe
# deb-src http://mirrors.linode.com/ubuntu/ xenial-updates universe
Output from https://repogen.simplylinux.ch that worked
#------------------------------------------------------------------------------#
# OFFICIAL UBUNTU REPOS #
#------------------------------------------------------------------------------#
###### Ubuntu Main Repos
deb http://us.archive.ubuntu.com/ubuntu/ xenial main restricted universe multiverse
deb-src http://us.archive.ubuntu.com/ubuntu/ xenial main restricted universe multiverse
###### Ubuntu Update Repos
deb http://us.archive.ubuntu.com/ubuntu/ xenial-security main restricted universe multiverse
deb http://us.archive.ubuntu.com/ubuntu/ xenial-updates main restricted universe multiverse
deb-src http://us.archive.ubuntu.com/ubuntu/ xenial-security main restricted universe multiverse
deb-src http://us.archive.ubuntu.com/ubuntu/ xenial-updates main restricted universe multiverse
apt-get update
do? Do you get any errors?/etc/apt/sources.list
.