Small-world networks interpolate between fully regular and fully random topologies and simultaneously exhibit large local clustering as well as short average path length. Small-world topology has therefore been suggested to support network synchronization. Here we study the asymptotic speed of synchronization of coupled oscillators in dependence on the degree of randomness of their interaction topology in generalized Watts-Strogatz ensembles. We find that networks with fixed in-degree synchronize faster the more random they are, with small worlds just appearing as an intermediate case. For any generic network ensemble, if synchronization speed is at all extremal at intermediate randomness, it is slowest in the small-world regime. This phenomenon occurs for various types of oscillators, intrinsic dynamics and coupling schemes.