Eu consegui isso seguindo o seguinte curso de ação:
1 / Primeiro, removendo lxc 1.0. Algo Algo
$: sudo apt-get purge lxc
2 / Limpar todas as dependências
$: sudo apt-get autoremove
3 / Instalando versão específica do lxc
$: sudo apt-get install lxc=0.9.0-0ubuntu3.6
4 / e terminando de instalar o docker novamente, seguindo estas instruções