I had a similar issue and it was quite annoying. My settlers would walk up to the wall on the edge of the region of the city they started in and just resettle. You have to actually move them into the new region then click settle there instead.
