Electrostatic self-assembly of colloidal and nanoparticles has attracted a lot of attention in recent years, since it offers the possibility of producing novel crystalline structures that have the potential to be used as advanced materials for photonic and other applications. The stoichiometry of these crystals is not constrained by charge neutrality of the two types of particles due to the presence of counterions, and hence a variety of three-dimensional structures have been observed depending on the relative sizes of the particles and their charge. Here we report structural polymorphism of two-dimensional crystals of oppositely charged linear macroions, namely DNA and self-assembled cylindrical micelles of cationic amphiphiles. Our system differs from those studied earlier in terms of the presence of a strongly binding counterion that competes with DNA to bind to the micelle. The presence of these counterions leads to novel structures of these crystals, such as a square lattice and a √3 x √3 superlattice of an underlying hexagonal lattice, determined from a detailed analysis of the small-angle diffraction data. These lower-dimensional equilibrium systems can play an important role in developing a deeper theoretical understanding of the stability of crystals of oppositely charged particles. Further, it should be possible to use the same design principles to fabricate structures on a longer length-scale by an appropriate choice of the two macroions.