TL; DR: Eu tinha instalado o Docker usando o "apt-get install docker.io". A instalação da versão mais recente após o link corrige o problema.
Após investigar o problema, parece que a versão do Docker no 15.10 não pode criar e inicializar corretamente a interface docker0. Na primeira execução (inicialização da estação de serviço), ela criará a interface, mas falhará ao inicializá-la e, na execução subseqüente (reinicialização da estação de serviço), ela será inicializada. Isso pode ser reproduzido consistentemente adicionando e excluindo a interface manualmente com brctl. Este bug foi corrigido no Docker mais recente.