Eu encontrei esta resposta em outro post. Aparentemente, com o 16.04, uma atualização e atualização automáticas do apt-get atualização que é realizada duas vezes por dia. link
Ainda não resolvi esse problema na minha instalação, mas quis retransmitir essa informação.
O dpkg e o apt-get foram desbloqueados na minha instalação após um atraso de 5 minutos após a inicialização.