apt - Recovering from a failed upgrade (14.04 -> 16.04, but probably applies to all versions)

I'm in the process of upgrading my Ubuntu system from 14.04LTS to 16.04LTS. (This is a server system, and is accessible through the command line only)

Anyway, I attempted to do the upgrade:

sudo do-release-upgrade 

...

and it failed:

Please report this as a bug and include the files
/var/log/dist-upgrade/main.log and /var/log/dist-upgrade/apt.log in
your report. The upgrade has aborted.
Your original sources.list was saved in
/etc/apt/sources.list.distUpgrade.

SystemError: E:Sub-process /usr/bin/dpkg returned an error code (1)

---

I rebooted my system, and I still have access to it. However, my system is only partially upgraded. I'm trying to figure out how to "complete" the upgrade:

It thinks I'm on 16.04:

lsb_release -a

LSB Version:    core-2.0-ia32:core-2.0-noarch:core-3.0-ia32:core-3.0 noarch:core-3.1-ia32:core-3.1-noarchh
Distributor ID: Ubuntu
Description:    Ubuntu 16.04.5 LTS
Release:        16.04
Codename:       xenial

Trying to manually do the update fails:

sudo apt-get update && sudo apt-get upgrade

Hit:1 http://mirrors.linode.com/ubuntu xenial InRelease                        
Hit:2 http://mirrors.linode.com/ubuntu xenial-updates InRelease                
Get:3 http://security.ubuntu.com/ubuntu xenial-security InRelease [107 kB]     
Fetched 107 kB in 10s (10.1 kB/s)                                              
Reading package lists... Done
Reading package lists... Done
Building dependency tree       
Reading state information... Done
Calculating upgrade... Done
The following packages have been kept back:

  parted
0 upgraded, 0 newly installed, 0 to remove and 1 not upgraded.

A dist-upgrade gives me the same result:

sudo apt-get dist-upgrade
Reading package lists... Done
Building dependency tree       
Reading state information... Done

Calculating upgrade... Done
The following packages have been kept back:
  parted
0 upgraded, 0 newly installed, 0 to remove and 1 not upgraded.

When I manually attempt to upgrade "parted", I get the following errors:

sudo apt-get --with-new-pkgs upgrade
Reading package lists... Done

Building dependency tree       
Reading state information... Done
Calculating upgrade... Done
Some packages could not be installed. This may mean that you have
requested an impossible situation or if you are using the unstable
distribution that some required packages have not yet been created
or been moved out of Incoming.
The following information may help to resolve the situation:

The following packages have unmet dependencies:

 libparted1.6-0 : Conflicts: libparted2 but 3.2-15ubuntu0.1 is to be installed
                  Recommends: libreiserfs0.3-0 but it is not installable
 libparted1.6-12 : Conflicts: libparted2 but 3.2-15ubuntu0.1 is to be installed
 libparted1.6-13 : Conflicts: libparted2 but 3.2-15ubuntu0.1 is to be installed
E: Broken packages

I (stupidly) thought that I should upgrade from 16.04 to 18.04, but when I run the command now, the system recognizes that the packages aren't all upgraded:

sudo do-release-upgrade

Checking for a new Ubuntu release
Please install all available updates for your release before upgrading.

So, how do I get the install to continue to complete? I have tried various commands without any success:

sudo dpkg --configure -a
sudo apt-get clean 
sudo apt-get update --fix-missing
sudo apt-get install --fix-broken