We have studied the phase behavior of concentrated aqueous solutions of cetylpyridinium bromide (CPB) and sodium 3-hydroxy-2-naphthoate (SHN) using X-ray diffraction and polarizing optical microscopy. The phase behavior of this system is found to be very similar to that of the cetyltrimethylammonium bromide (CTAB)-SHN-water system, reported by us recently (Ghosh, S. K., et al. Langmuir, 2007, 23, 3606), but with the important difference that the mesh-like aggregates in the present system have square symmetry, instead of the hexagonal symmetry seen in the earlier case. A random mesh phase without long-range correlations of the in-plane structure, as well as an ordered mesh phase, where the mesh-like aggregates lock into a three-dimensional lattice, are observed, as in the CTAB-SHN-water system. The mesh-like aggregates do not form when the hydroxynaphthoate counterion is replaced by either salicylate or tosylate, which are also known to bind strongly to the surfactant micelle. Instead, the phase behavior of these ternary mixtures is akin to that of the CPB-water binary system; the only liquid crystalline phase observed being the hexagonal phase made up of cylindrical micelles. These results show the extreme sensitivity of the structure and stability of mesh phases to subtle changes in the interheadgroup interactions.