Do the openstack images use debootstrap as a package resolver? If so, yeah, that broke for most nontrivial installations in stretch.