package libpython3.5-minimal:amd64 3.5.1-10 failed to install/upgrade: package is in a very bad inconsistent state; you should reinstall it before attempting configuration

[Mercucio]

unkown

ProblemType: Package
DistroRelease: Ubuntu 16.04
Package: libpython3.5-minimal:amd64 3.5.1-10
ProcVersionSignature: Ubuntu 4.4.0-16.32-generic 4.4.6
Uname: Linux 4.4.0-16-generic x86_64
ApportVersion: 2.20.1-0ubuntu1
Architecture: amd64
Date: Fri Apr 1 18:35:38 2016
ErrorMessage: El paquete está en un estado grave de inconsistencia - debe reinstalarlo antes de intentar su configuración.
InstallationDate: Installed on 2016-03-07 (24 days ago)
InstallationMedia: Ubuntu 16.04 LTS "Xenial Xerus" - Alpha amd64 (20160304)
RelatedPackageVersions:
 dpkg 1.18.4ubuntu1
 apt 1.2.9
SourcePackage: python3.5
Title: package libpython3.5-minimal:amd64 3.5.1-10 failed to install/upgrade: El paquete está en un estado grave de inconsistencia - debe reinstalarlo antes de intentar su configuración.
UpgradeStatus: No upgrade log present (probably fresh install)

[Launchpad Janitor (janitor)]

Status changed to 'Confirmed' because the bug affects multiple users.

[Alberto Salvia Novella (es20490446e)]

This breaks the distribution upgrade at bug #1551623.

[Matthias Klose (doko)]

this is not a package specific issue

[Vidar Hoel (vidar-hoel)]

This bug affected my too, but I was able to solve it.

Short answer:
dh-python is dependent on python3, python3 is dependent on dh-python. Solve it by running:
sudo dpkg --force-configure-any --configure dh-python

Long answer:
I did a do-release-upgrade on my Ubuntu Gnome 15.10 to 16.04, but it failed a gconf2, with the massage it was dependent on python3.5, but it was not configured, and I was unable to configure it. However, I started with:
sudo dpkg --configure python3 -> Didn't work because it was dependent on python3.5, so I did a
sudo dpkg --configure python3.5 -> Didn't work because it was dependent on (see next line), so I did a
sudo dpkg --configure libpython3.5-stdlib
sudo dpkg --configure python3.5
sudo dpkg --configure python3
sudo dpkg --configure libpython3-stdlib
and then I ran:
sudo dpkg --configure python3 --> Which did not work, becasue it was dependent on dh-python, so I ran
udo dpkg --configure dh-python --> Which did not work either, because it was dependent on python3.

I was able to get past this by running:
sudo dpkg --force-configure-any --configure dh-python

And now everything seems to work.