I found a similar problem in that once I had soldiers and my city was at a certain level, the soldiers would get stuck.
They wouldn't be able to move out because there were buildings in the way.
I believe we should be able to have our own troops (and/or allies troops) be able to move over our own cities to be able to move beyond them.
I found this to be a huge problem to gameplay, and possibly needs to be addressed in this beta, unless there is something I too am missing.
Again I will plug that the cities are too large for scale.... Reduce the size of the cities, and bring them in to a realistic scale (ie. make the large squares divided into 9 instead of 4, or scale the cities down by 1/4). Perhaps then we might have less blocking as well.