Comment 3 for bug 869310

I find that instances stuck as "terminated" typically come from a communication break-down to the host server e.g. if the nova-compute service is not running the terminated instance will stay as terminated until the node come back online.

Could that be the case here ?