Starting from a glassy suspension of star polymers in molecular solvent, we add linear homopolymer with a fixed size ratio and ever increasing concentration, hence diluting the glass and eventually approaching the regime of stars in polymer matrix. We show that we can quantitatively decompose the rheology of the mixtures into colloidal star and linear polymer contributions by accounting for the osmotic shrinkage of the stars due to the added polymers. We also estimate the effective star overlap concentration in the mixtures and show how the rheological properties change at the crossover concentration, where the number of star-particle contacts decreases and the star repulsions weaken and eventually become attractive upon increasing the linear polymer concentration. The attraction is accompanied by a phase separation, pointing to the presence of unstable regions in the star/linear polymer phase diagram, where gelation results from an arrested phase separation. The crossover concentration is also probed by nonlinear rheological measurements. These findings are of generic nature for soft colloidal mixtures and suggest guidelines for tailoring their rheology and phase/state behavior.