I'm fairly sure that there must be a connection between a city with a harbour and a landlocked capital by road. That is, if your capital is landlocked, and City A just has a harbour but no land connection, then I'm fairly sure there needs to be a City B with a harbour that is connected to the capital in order for City A to get a trade route. Harbour, IIRC, have automatically established connections between them, so just imagine a road between City A and City B, required to link up with the road continuing to the capital. (could be incorrect, but I'm fairly sure)