Recent experiments show a strong rotational-diffusion enhancement for self-propelled microrheological probes in colloidal glasses. Here, we provide microscopic understanding using simulations with a frictional probe-medium coupling that converts active translation into rotation. Diffusive enhancement emerges from the mediums disordered structure and peaks at a second-order transition in the number of contacts. Our results reproduce the salient features of the colloidal glass experiment and support an effective description that is applicable to a broader class of viscoelastic suspensions.