We present precision Monte Carlo data and analytic arguments for an asymmetric exclusion process, involving two species of particles driven in opposite directions on a 2×L lattice. To resolve a stark discrepancy between earlier simulation data and an analytic conjecture, we argue that the presence of a single macroscopic cluster is an intermediate stage of a complex nucleation process: in smaller systems, this cluster is destabilized while larger systems form multiple clusters. Both limits lead to exponential cluster size distributions, controlled by very different length scales.