keine Straßenverbindung zu Nachbarstadt

Dann ist die Stadt nicht direkt in deiner Region. Oder warte einfach ein bischen.

Wie denn warten, verändert sich die Region automatisch?

Bei mir hat es auch mal gut 2 Stunden gedauert bis die eine Stadt mit der anderen verbunden war.

Nein, wenn die Stadt in deiner direkten Region steht, müsste es gehen.

Man muss eine Verbindung per Zug oder Autobahn haben

Die 16er Regionen sind z.B. oft Viertegeilt, wo immer nur 4 Regionen direkt verbunden sind

Nein die Region verändert sich nicht Automatisch zumindest was das Terrain angeht.
Sind die Städte die Handel treiben wollen mit der Autobahn verbunden ?
Weil in einer Region können jeweils nur 4 Städte mit einander Handel treiben ( so habe ich es zumindest mitbekommen und selbst erlebt, verbessert mich bitte wenn ich mich irre ).
Ich habe mal ein Bild hoch geladen um die Sache zu verdeutlichen.

Du brauchst eine Autobahn-, Schiffs- oder Zugverbindung (abgesehen vom Internationalen Flughafen).
Es ist nicht immer möglich Direkten Handel zu führen ohne ein Umschllagplatz mit einer Güterzugabteilung zu haben oder halt ein Hafen wenn es sich anbitet.