We have studied mixtures of an anionic surfactant (deuterated sodium dodecyl sulfate, SDS-d) and cationic polyelectrolytes with different charge densities (10%, 30%, 60%, and 100%) using small-angle neutron scattering (SANS). Near compositions corresponding to charge neutralization, the solutions phase separate into a complex phase (precipitate) consisting of, in the cases of 30%, 60%, and 100% charge density, a two-dimensional (2D) hexagonal lattice of close-packed cylindrical micelles and a clear liquid. When either polyelectrolyte with charge density less than 100% or SDS-d is present in sufficient excess, the solution becomes clear and isotropic, and from the scattering data we may conclude that prolate or rod-shaped micelles are present. The micelles are seen to grow in length with increasing SDS-d concentration and polyelectrolyte charge density from about 80 Å to 550 Å, whereas the cross-sectional radius is 15 Å and approximately constant. The number of micelles per polyelectrolyte chain is found to be slightly larger than unity (1-6). In some of the (turbid) samples rod-shaped micelles are found to coexist with larger polyelectrolyte-surfactant complexes. Solutions consisting of 10% charged polyelectrolyte and SDS-d are very viscous and gellike, and the complex phase is much less defined with a much larger distance between adjacent aggregates in the complex phase.