The volume and structural changes upon replacement of oppositely charged network counterions for oppositely charged macroions in cross-linked polyelectrolyte gels have been investigated by Monte Carlo simulations using a coarse-grained model. Initially, the gel deswells, but after an approximately equivalent amount of macroions, the gel starts to swell again. The deswelling effect is greatest for small and highly charged macroions. The role of different network properties on the deswelling has also been examined. The initial deswelling is understood in terms of a replacement of confined counterions with macroions, thereby reducing the osmotic pressure originating from the counterions. At these conditions, macroions are located near network nodes with various degrees of network chains wrapping them. At charge equivalence, a profound change in the network structure has appeared. At these conditions, the cohesive electrostatic interaction and the excluded volume effect of the macroions strongly influence the equilibrium volume of the gel. Our model system reproduces many characteristic experimental observations of polyelectrolyte gels containing oppositely charged surfactants.