Phase behavior and rheology of polymer mixtures comprising aqueous solutions of oppositely charged polyelectrolytes are investigated. Emphasis is put on the effects of hydrophobic modification of the polymers and addition of salt. The associative phase separation usually observed when mixing oppositely charged polyelectrolytes is effectively prevented over a large miscibility region for the hydrophobically modified polymers. Also, in the extended one-phase region, the viscosity is 3-4 orders of magnitude higher for mixed polyelectrolyte systems compared to that observed for either one of the polymers. Addition of ordinary electrolytes to the mixture decreases the viscosity strongly, and at higher electrolyte contents a phase separation is induced. A mechanism explaining the observations is proposed.