Testei também no Ubuntu 16.04 padrão (=Unity), igualmente usando o release 2, portanto, também com o kernel 4.8 mencionado.
Mesmo e idêntico resultado, mesmo erro da primeira vez, solucionado ao instalar zlib1g-dev, então o Python 3.6.0 compilou e instalou sem erros.