I sent a caravan, protected by a stack of warriors (due to a pesky wandering bear that ate my last one) to another of my cities. When the stack reached the city, the caravan didn't create the trade route. The only way I could get the caravan to create the trade route was to move the caravan out of the city and back in.
