Answered on behalf of the OP who answered their own question as follows:
Note: posted by the original poster and just copied here
Figured it out. Lookup values in original data frame (CountryCity) and lookup data frame (routes_lookup) must be of same type (and just because both are characters, the former can't have the characters all smashed into one entry). In addition, the colname of the "terms" parameter must be specified in the function call.
spint <- as.data.frame(shortest.paths(g_all))
cities <- as.data.frame(matrix(rownames(spint)), byrow=TRUE)
CityCountry <- data.frame(City = as.character(cities$V1))
routes_lookup <- subset(routes_sa, select=c("City_Source", "Country_Source"))
CityCountry$Country <- lookup(CityCountry$City, routes_lookup)