My king recently abdicated his throne and I've been without a kingdom since. Yesterday a small button in the bottom left of my screen popped up and suggested that I relocate my village. When I clicked on it expecting two kings to choose from, it actually just gave me a message saying "No empty starting locations found near you. Please try again later." or something like that.
Now that button has disappeared. I am a governor without a king and really need to relocate into another kingdom or I'm going to end up a farm really soon!
Oh, and yes, I do fill all the criteria for relocation - single village, governor without a king, low population.