Starting Lab is stuck at: "We couldn't power on those instances right now because some are already busy."

After a few days away from the lab, it won't start anymore. It always failing with:
We couldn't power on those instances right now because some are already busy.

This comes from a single machine in the Lab, starting the others one by one does work. Also reverting the complete lab or the single machine does not work, failing with a similiar message.

We couldn't revert those instances right now because some are already busy.