Using Ubuntu 16.04 with the 3.6.0 tag I was also able to reproduce the same error reported:

import socket

h = "0123456789012345678901234567890123456789012345678901234567890123.example.com"
socket.gethostbyname(h)

Traceback (most recent call last):
  File "/home/agnosticdev/Documents/code/python/python-dev/cpython-3_6_0/Lib/encodings/idna.py", line 165, in encode
    raise UnicodeError("label empty or too long")
UnicodeError: label empty or too long

The above exception was the direct cause of the following exception:

Traceback (most recent call last):
  File "host_test.py", line 8, in <module>
    socket.gethostbyname(h)
UnicodeError: encoding with 'idna' codec failed (UnicodeError: label empty or too long)


It looks like the hostname being 64 characters long is the issue in that it cannot be encoded.  Thus falling into the UnicodeError being raised in idna.py:
            # ASCII name: fast path
            labels = result.split(b'.')
            for label in labels[:-1]:
                if not (0 < len(label) < 64):
                    raise UnicodeError("label empty or too long")
            if len(labels[-1]) >= 64:
                raise UnicodeError("label too long")
            return result, len(input)

I did some work on this to try and resolve this, but ultimately it was not worth committing so I wanted to report my findings.