Often enough, someone creates a new keyspace using NetworkTopologyStrategy replication and the datacenter names aren't correct. When this happens, the driver falls back to looking at all token ranges to determine where replicas for the keyspace exist. When that happens, Cassandra connections can take a very long time on large clusters.
The current version of the driver doesn't log the keyspace name, or track how long it takes to process each keyspace. Without this data, finding the bad keyspace is a lot more difficult. Obviously, bad replication configuration shouldn't happen, but sometimes it does.
We have also seen these long token map rebuilds on keyspace with valid replication strategies, but it is far less frequent.
I have attached a patch, but am happy to submit a pull request as well.
Added debug logs before and after (with elapsed time) the computation.