Você deve executar:
lxc-start -F -l DEBUG -n <container name>
Para descobrir a causa raiz do problema.
No meu caso particular, foi:
Permission denied - could not access /var/lib/lxc. Please grant it 'x' access, or add an ACL for the container root.
Que foi corrigido por chmod +x /var/lib/lxc