Attempting to upgrade from Ubuntu Server 16.04 to 18.*

I had the same issue. I did:

sudo apt-get update 
sudo apt-get upgrade -y
sudo apt-get dist-upgrade
sudo do-release-upgrade

Hope this helps!

In case someone is unable to solve this with the accepted answer. I had a third-party-repository with a broken-dependency, which showed up via sudo apt list --upgradable - the package in question did require another package, which was unavailable due to an error of the packager.

I solved it by disabling all third party repositories (as root):

cd /etc/apt/sources.list.d/
for i in *.list; do
  mv $i ${i}.disabled
done

Then cleaned the update state:

apt clean
apt autoclean

and restarted the update process:

do-release-upgrade