O problema parece ser o universo e multiverso xeno-segurança repos são corruptos.
Consegui corrigir o problema editando /etc/apt/sources/list
e comentando estas linhas:
#deb http://ports.ubuntu.com/ubuntu-ports xenial-security universe
#deb-src http://ports.ubuntu.com/ubuntu-ports xenial-security universe
#deb http://ports.ubuntu.com/ubuntu-ports xenial-security multiverse
#deb-src http://ports.ubuntu.com/ubuntu-ports xenial-security multiverse
Moral da história, cuidado com os pacotes mantidos pela comunidade e proprietários!