We've gone through this pain as well and here is what we have found to help:
Recently rejoin-stack.sh was removed as an option. DevStack is not intended to support restoring a running stack after a reboot.
Instead, you will need to run stack.sh and create a new cloud.
Remember to put the things that you always want done (like adding your public key, creating special flavors, etc) into local.sh and they will be done at the end of stack.sh.
Please remember => DevStack is not meant and should not be used for running a cloud.
If that is your need, please investigate one of the many alternatives that are designed and tested for cloud operation, including upgrades.