apt - Cannot install GDB on Ubuntu 17.10 due to Python dependency issues

I had to uninstall GDB just to upgrade to 17.10, but now I can't get it installed again.

sudo apt install gdb
Reading package lists... Done
Building dependency tree
Reading state information... 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:
 gdb : Depends: libpython3.6 (>= 3.6.0~b2) but it is not going to be installed
E: Unable to correct problems, you have held broken packages.

So I went down the dependency chain:

The following packages have unmet dependencies:
 libpython3.6 : Depends: libpython3.6-stdlib (= 3.6.3-1ubuntu1) but 3.6.3-1+xenial2 is to be installed
E: Unable to correct problems, you have held broken packages.

Why is there a reference to Xenial? And why can't it be upgraded?

It seems that GDB requires a specific version, that doesn't match the xenial one. Attempting to remove the package is nigh impossible because of the number of packages which depend on libpython3.6.

Further information:

apt-cache showpkg
Package: libpython3.6
Versions:
3.6.3-1ubuntu1 (/var/lib/apt/lists/archive.ubuntu.com_ubuntu_dists_artful_main_binary-amd64_Packages)
apt-cache showpkg
Package: python3.6
Versions:
3.6.3-1+xenial2 (/var/lib/dpkg/status)
3.6.3-1ubuntu1 (/var/lib/apt/lists/archive.ubuntu.com_ubuntu_dists_artful_main_binary-amd64_Packages)

So my guess is that APT doesn't have a handle on where it got the +xenial2 package from.

The issue here is that the package version 3.6.3-1+xenial2 was considered newer than 3.6.3-1ubuntu1.

The fix was to downgrade the package, even though the actual python version was the same.

This was a weird issue to fix because I hadn't used any PPAs which N0rbert suggested, and the package was considered newer than the main repos one (although it wasn't).

This may have been because I had first installed this system on Xenial, which might have had something to do with why I had that strange version installed. (Potentially a backport with different naming scheme?)

On downgrading packages: How to downgrade a package via apt-get?