Eu resolvi esse problema - é importante notar que minhas habilidades com o docker e o AppArmor são rudimentares, então não tenho 100% de certeza sobre o que está acontecendo aqui.
Quando apliquei pela primeira vez a solução AppArmor (uma reclamação por sessão), funcionou. Em seguida, desativei o perfil em geral para obter consistência nas reinicializações (conforme recomendado no wiki do Ubuntu ):
sudo ln -s /etc/apparmor.d/docker /etc/apparmour.d/disable/docker
Quando eu excluí a entrada em /etc/apparmour.d/disable e tenho apenas o conjunto de reclamações, o docker começa a funcionar novamente.
Para referência, eu configurei uma VM do Ubuntu 15.04 nesta AM e tive exatamente o mesmo problema - foi assim que encontrei a solução.