Eu tive o mesmo erro em uma das minhas VMs, as outras 2 e o hipervisor estavam bem. Mesma versão (16.04.3), não é uma pista do que a causou. É um bug conhecido.
Tenho algum alívio aqui
Modifique o arquivo /usr/share/pyshared/lsb_release.py
line 41 de:
RELEASES_ORDER.sort(key=lambda n: float(n[0]))
para:
RELEASES_ORDER.sort(key=lambda n: float(n[0].split()[0]))
Corrigido o problema para mim. Crédito completo para SHIINA Hideaki (shiina) na barra de lançamento do bug do Ubuntu. Estou apenas repostando aqui.